渐进分析

随着硬件水平的飞速发展，计算机的计算性能不断提升，对于小规模的数据，计算所需的时间差异一般不大。因此我们通常关注 数据规模逐渐扩大至极限时，时间复杂度的极限情形（渐近分析，asymptotic analysis），以此来判断一个算法需要的计算资源。

大 O 表示法定义：$T(n) = O(f(n))$， 当且仅当 存在常数 $c, n_0 > 0$, 使得对于所有的 $n \geq n_0$：

$$T(n) \leq c\cdot f(n)$$

Omega-n 定义：$T(n) = \Omega(f(n))$, 当且仅当 存在常数 $c, n_0 > 0$, 使得对于所有的 $n \geq n_0$：

$$T(n) \geq c\cdot f(n)$$

最后是 $\theta(n)$, 它的定义是：$T(n) = \theta(f(n))$, 当且仅当 $T(n) = O(f(n))$ 并且 $T(n) = \Omega(f(n))$。

直觉上，$O(f(n))$ 表示的， 是算法复杂度与 $f(n)$ 同级别及以下的情况（下限及以下），或者说 $O(f(n))$ 以 $f(n)$ 为上界。而 $\Omega(f(n))$ 相当于是 $f(n)$ 复杂度的上限及以上。

不过平常使用的时候，似乎不太常会使用到上述的描述方法的细节差别（在 课程中，老师有时会使用 $O(n)$ 表示，有时候会使用 $\theta(n)$ 表示）。

具体分析时，一个算法的计算资源消耗情况 主要是由其最高次项决定，因此，在分析时，我们会忽略算法复杂度中的 低阶项 以及 常数因子。常见的复杂度之间的关系如下：

$$1 < klogn < n < nlogn \approx log(n!) < n^k < a^n < n! < n^n$$