快慢的秘密：算法复杂度

同样是找一本字典里的字，你一页页翻要翻半天，按拼音直接翻几秒就到。同样是排序，有的算法快有的慢。怎么衡量一个算法快不快、好不好？程序员用一种叫“复杂度”的标尺，它告诉你：数据变多时，算法会慢多少。学会看复杂度，就能选出又快又好的算法。

复杂度怎么算

复杂度用一个大 O 加括号表示，比如 O(n)、O(n²)。O(n) 意思是：数据量是 n，干活次数跟 n 差不多。比如找一摞牌里某一张，一张张看，最多看 n 次。O(n²) 是数据量 n，干活次数约 n×n。比如比较 n 张牌两两大小，要 n² 次。n 小的时候差不多，n 大了就天差地别。

举个例子：在 10 个里找东西，O(n) 最多 10 次，O(n²) 是 100 次，都很快。但在 100 万个里找，O(n) 是 100 万次（电脑秒完），O(n²) 是 1 万亿次（要算好久）！所以数据量大时，选对算法特别重要。还有更快的：二分查找是 O(log n)，100 万个里找最多 20 次就够——这就是算法的力量。

• O(n)：数据变多，时间按比例变长
• O(n²)：数据变多，时间按平方变长
• O(log n)：数据变多，时间几乎不变
• 数据量越大，算法差异越大
• 选对算法，比换快电脑还管用

复杂度不只是时间，还有“空间复杂度”——占多少内存。有时为了快，要多用内存；有时为了省内存，要慢一点。程序员常在这两者间权衡。理解复杂度，能让你写出又快又省的程序。很多面试考的就是：能不能分析复杂度、能不能把慢算法改快。

聪明的方法，比蛮干快千万倍。——编程小语