##时间复杂度表示方法

  • 如果存在正常数c和n,使得当N ≥n时 T(N) ≤cf(N)，则记为T(N) = O(f(N));
  • 如果存在正常数c和n,使得当N ≥n时 T(N) ≥cf(N)，则记为T(N) = Ω(f(N));
  • 如果存在正常数c和n,使得当N ≥n时 T(N) =cf(N)，则记为T(N) = Θ(f(N));
  • 如果存在正常数c和n,使得当N ≥n时 T(N) <cf(N)，则记为T(N) = o(f(N));

实际情况中主要是使用大O表示法

##有以下几个法则

  • 如果T1(N) = O(f(N))且T2(N)=O(g(N)),那么:
    1. T1(N) +T2(N) = max(O(f(N)) , O(g(N)))
    2. T1(N) T2(N) = O(f(N) g(N))
  • 如果T(N)是一个k次多项式，则T(N) = Θ(N^k)
  • 对于任意常数k，log^kN = O(N)

##常见的时间复杂度模型

  • c 常数
  • logN 对数级
  • log^2N 对数平方根
  • NlogN
  • N^2 平方级
  • N^3 立方级
  • 2^N 指数级