算法时间复杂度

时间复杂度计算概略地讲，就是“suppress constant factors and lower-order terms”

Formal Definition: $T(n) = O(f(n))$
if and only if exist constants $c, n_0$ such that $T(n) le cf(n)$
for all $n gt n_0$

即 $n rightarrow +infty$ 时，$cf(n)$ 为 $T(n)$ 上限

Formal Definition: $T(n) = Omega(f(n))$
if and only if exist constants $c, n_0$ such that $T(n) ge cf(n)$
for all $n gt n_0$

即 $n rightarrow +infty$ 时，$cf(n)$ 为 $T(n)$ 下限

Formal Definition: $T(n) = Theta(f(n))$
if and only if $T(n)=O(f(n))$ and $Omega(n)=O(f(n))$

即 $n rightarrow +infty$ 时，$cf(n)$ 既能作 $T(n)$ 下限也能作上限，