算法评测

算法评测——复杂度记法

刚才说过，线性查找的计算量为O(n)，二分查找的复杂度为O(log n)。大多情况下，算法的复杂度可以这样定量评测。算法评测一般使用复杂度记法（Order记法）。

复杂度记法表示的含义是，当算法的输入大小为n时，大致需要这么多的计算量。

花费时间与n的大小无关，能在固定时间内完成的处理，其复杂度为O(1)。例如从散列中查找数据，虽然要计算散列函数，但散列函数计算不依赖于n，所以复杂度为O(1)。而散列搜索中，给定键的值（几乎）是唯一的，因此通过键搜索值的处理也是O(1)（也依赖于具体实现）。因此，散列搜索整体复杂度为O(1)^[1]。

如前所见，线性查找要从开头开始查找，最大要查找n次。

某些情况下只需一次就能找到，但复杂度记法并不考虑这种特殊情况，而是表示平均值或最大值。因此记为O(n)。二分查找为O(log n)。

像这样用复杂度记法表示各种算法，即可比较算法的性能。线性查找和二分查找分别为O(n)和O(log n)，因此二分查找的计算量比较少^[2]。

各种算法的复杂度记法

各种算法的复杂度记法中，下述几种计算量经常出现。

— O(1) < O(log n) < O(n) < O(nlog n) < O(n²) < O(n³) … < O(n^k) < O(2ⁿ)

越往右，复杂度越大。处理大规模数据时，也就是说n比较大时，实用算法也就到O(n logn)附近。再高，复杂度就会随着n的增加而急剧增大，经常导致计算无法结束。

感觉上而言，O(log n)比O(n)要快很多，O(n)和O(n log n)的差距不是很大，O(n)和O(n²)之间的鸿沟决定着着计算能否完成……。

关于速度问题，如果相当复杂的算法能用O(n²)的计算完成，那也可以说“相当快”了，毕竟速度取决于算法中的计算本身。例如，一般的基于比较的排序算法无论怎么优化，也不可能比O(n logn)快，这一点在理论上可以证明。因此，排序算法能达到O(n logn)，就可以认为是高速算法。

复杂度的概念不仅用于表示计算的时间，也可以用于表示空间。也就是说，复杂度记法不仅可以表示执行时间、操作步骤数，还可以表示内存使用量等。

 

 

上面讲述了算法评测。更为详细的内容，请参考讲解算法的书籍。

算法评测

— 复杂度记法

— 复杂度

— 时间复杂度（执行时间、操作步骤数）

— 空间复杂度（内存使用量）

刚才说过，线性查找和二分查找相比，数据量变大后，计算时间就会出现巨大差距。这里的重点不是复杂度记法本身，而是利用复杂度记法比较算法时，对算法间差距的感觉。就是说要掌握O(log n)和O(n)在n增大时，对于复杂度差距的感觉。

再看个身边的例子。准备一张纸巾，然后将其多次对折。到底能对折多少次呢？第一次只需对半折叠即可，完全没问题。第二次、第三次、第四次直到第五次应该也没问题。但第六次就比较难折了，第七次和第八次完全折不动而不得不放弃。可能有人会想“折100次肯定没问题！”，而实际上7次就是极限了。为什么呢？

折纸所需的劳动量，依赖于要折的纸张的厚度。假设这个厚度最初为1mm，那么第一次折叠之后就是2mm。两次折叠后是3mm……不对，是4mm。

这样，厚度是1→2→4→8→16→32…这样增加的。可以认为，设折叠次数为n，计算量就按照2ⁿ增长。刚才看到，O(2ⁿ)是个相当大的复杂度，因此纸巾在n=8时无法折叠也就可以理解了。

另外有文章介绍过，厚度为0.11mm的卫生纸折叠25次后会达到富士山的高度^[3]。要折叠富士山那么高的纸……一般方法绝对做不到吧。

对算法中指数增加、对数增加的感觉

计算量按照指数增加的算法，只需一点点数据量，计算量就会变得庞大无比。与指数相反，只以对数增加的O(log n)的算法，即使数据量变得非常大，也只需一点计算量就能解决，这点也能直观地理解吧。

在思考算法复杂度时，这种感觉是最重要的。例如要操作的数据有1000万条，如果能选择对数算法，那么只需几十次计算就可以了。相反，如果选错了算法，使用O(n²)或O(2ⁿ)的算法实现的话，写出的程序即使只有几百条数据，也要浪费相当多资源。

 

本文节选自《大规模WEB服务开发技术》一书

图书详细信息:http://blog.chinaunix.net/space.php?uid=13164110&do=blog&id=2211482