渐进时间复杂度

时间复杂度是衡量算法优劣程度的一个重要标准，它意味着算法在最坏情况下的运行速度.

假如我们要计算 $\sum_{i=1}^n i$，一种简单粗暴的方式是直接写一层循环，如果这样，我们一共就要进行 $n$ 次加法，当 $n$ 不断增长的同时，我们的运算次数也会随着线性增长，所以我们说，这个算法的时间复杂度是 $\mathcal{O}(n)$ 的.

这里的 $\mathcal{O}$ 记号到底是什么意思呢？$\mathcal{O}(n)$ 本质上是一个集合，表示所有的，运算次数随着数据规模线性增长的算法的效率。

举个例子，如果我们的算法进行了两次求和的操作，我们就要进行 $2n$ 次加法，它的时间复杂度并不是 $\mathcal{O}(2n)$，仔细想想就会发现，当 $n$ 大到一定程度的时候， $n$ 和 $2n$ 的区别并不算大。

这时候有人就要问了，什么才叫“不算大”？当 $n$ 越来越大的时候，$n$ 和 $2n$ 相差的明明会越来越多。

我们是这样解释的，虽然他们的差值会变大，但是他们的比值永远是一个常数，计算它们所花费的时间也只是两倍的关系而已，但假如现在有一个时间复杂度为 $\mathcal{O}(n^2)$ 的算法，也就是计算规模为 $n$ 的问题需要常数倍于 $n^2$ 的计算量，比较它与 $\mathcal{O}(n)$ 的算法就会发现，当 $n$ 为 $10^8$ 时，后者所要花费的时间已经是前者的 $10^8$ 倍了！

回到最开始的问题，计算这个和还有一种方法是公式：小学的时候我们就学过等差数列的求和公式。 $$ \sum_{i=1}^n i=\frac{1}{2}n(n+1) $$ 这次，无论 $n$ 有多大，我们都只需要计算三次乘法和一次加法（或者说，一次加法，一次乘法和一次除法）即可，我们可以认为，单次的加、减、乘、除、取模以及位运算都是 $\mathcal{O}(1)$ 的，于是上面算法的时间复杂度就是 $\mathcal{O}(1)$ ，这表明程序的运行速度和 $n$ 没有任何关系.

我们这样定义两个时间复杂度是否相同：对于两个计算规模对于 $n$ 的函数为 $T(n)$ 和 $S(n)$ 的程序，称它们时间复杂度相同，当且仅当在 $n$ 趋近于无穷大时，$T(n)$ 与 $S(n)$ 的比值为常数，写成极限的式子就是 $$ \lim_{n \to +\infty} \frac{T(n)}{S(n)} = C \ne 0 $$ 若该极限为无穷大，则 $T(n)$ 的时间复杂度要高于 $S(n)$ ，若为 $0$，则 $T(n)$ 的时间复杂度低于 $S(n)$。

于是我们可以正式解释 $\mathcal{O}$ 记号了：它描述了所有计算规模为 $T(n)$，满足 $\lim_{n \to +\infty} \frac{T(n)}{n}=C$ 的算法，我们在写 $T(n)=\mathcal{O}(n)$ 时，这个等号本质上是集合语言中的 $\in$，因此自然不能写作 $\mathcal{O}(n)=T(n)$。

类似的，假如时间复杂度中含有对数函数，我们是不写底数的，这是因为我们总可以用换底公式将不同的底数变为常数倍的差距，直接记作 $\mathcal{O}(\log n)$。

还有关键的一点是，在最开始说这是衡量算法在最坏情况下的运行速度，这个最坏情况，具体来说是：假如现在有一种算法能在平均 $\mathcal{O}(n)$ 的时间内解决某个问题，但是在某些特殊情况下，它的时间复杂度是 $\mathcal{O}(n^2)$，我们就不能说它的时间复杂度是 $\mathcal{O}(n)$ ，尽管这些特殊情况的条件可能很苛刻，但它们确实存在，我们就只能说算法的时间复杂度是 $\mathcal{O}(n^2)$。例如你不可以在最开始的例子中说，当 $n=1$ 的时候时间复杂度是 $\mathcal{O}(1)$，因此该算法的时间复杂度就是 $\mathcal{O}(1)$。