算法时间复杂度

Coursera 上 Algorithms: Design and Analysis, Part 1 by Tim Roughgarden 的学习笔记。第二课，有关时间复杂度。

The Gist

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

Big-Oh Notation

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)$ 上限

Omega Notation

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)$ 下限

Theta Notation

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)$ 下限也能作上限，