讨厌算法的程序员 | 第四章 时间复杂度

增长量级

函数的增长量级

上一篇算法分析基础中，我们分析了插入排序，知道了其最好情况下的运行时间为T(n) = an + b，最差情况下的运行时间为T(n) = an2 + bn + c。表达式中的常量a、b和c（实际上都是依赖每行代码的执行时间ci）进一步抽象了每行代码的执行时间，而凸显出输入规模n与运行时间T的关系。

然而这样还不够，还有进一步抽象的空间：即人们真正感兴趣的是运行时间随输入规模增长的增长率或增长量级。也就是说，当n越来越大时，T的增长是何种量级？我们知道，当n的值很大时，低阶项对T的贡献就没那么重要了，同时，最重要的高阶项的常量系数对T的贡献也没那么重要了。

对于插入排序最差情况来说，当忽略掉低阶项以及高阶项的常数系数，就只剩下了n2。插入排序最差情况的运行时间，可记做T(n) = Θ(n2)，其中Θ称作渐进记号，这种简化成为渐进分析。

渐进分析强调的是，对于足够大的输入，运行时间中的倍增常量和低阶项被输入规模本身的影响所支配。尽管有时在一个小输入下，一个运行时间具有较低增长量级的算法（比如T(n) = 5n)），比一个运行时间具有较高增长量级的算法(比如T(n) = n2)，需要更多的时间。

时间复杂度

《算法导论》中的整个第一部分（第1章到第5章），一直没有发现“时间复杂度”这个我们非常熟悉的名词及定义（英文版未考证），尽管书中一步步引导出的“算法运行时间”，以及“渐进记号”其实就是在说“时间复杂度”。到了第二部分（第6章），又开篇冒出了“时间复杂度”这个词，反而有点不适。这可能与中文版是由7个人翻译的有关。

刚好手边有程杰的《大话数据结构》一书，这里引用下其对“时间复杂度”的定义，算是有个交待。

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间度量，记作：T(n) = Ο(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中f(n)是问题规模的函数。

渐进记号

细心的读者可能发现了，上面的增长量级一节与时间复杂度一节分别用到了两种不同的渐进符号，Θ和Ο，前者发音Theta，后者发音Omicron，它们都是希腊字母。

通常所说的算法时间复杂度不都是用的后一种Ο么（有时也叫大Οmicron）？

到这里，《算法导论》的厉害之处就彰显无余了。它不仅介绍了Θ和Ο，还介绍了Ω（大Omega），ο（小Omicron），ω（小Omega）5种不同的渐进记号，每种记号都体现了不同的渐进分析方法。

出于实用性的考虑，这里只简单说下Θ与Ο的异同。对其余渐进符号，用到之处会再解释。

对于T(n) = an2 + bn + c, 既可以记作T(n) = Θ(n2)，也可以记作 T(n) = Ο(n2)。

对于T(n) = an + b, 既可以记作T(n) = Θ(n)，也可以记作T(n) = Ο(n)，还可以记作T(n) = Ο(n2)。

这是因为Θ是一种紧确性的表示，而Ο是一种非紧确性、只描述了上限的表示。

《算法导论》中的翻译的这个词“紧确”，还是很形象的。我再说的直白点，就是绘制出的函数图形，是否比较“贴合”。

我们看到的大部分书中都是在用Ο（大Omicron）表示时间复杂度，但通常都是选择了一个紧确性的函数。比如说，T(n) = an + b，T(n) = Ο(n)，T(n) = Ο(n2)都对，但是会选择前者T(n) = Ο(n)。