硬件强悍，算法是否已经不再重要？

本文翻译自程序员的问答社区 stackexchange.com 上的一个提问：追求算法（特别是普遍高效的）已经不再重要。因为现在计算机硬件的成本，比起以前已经很便宜，是否意味着算法和改进算法的技能已经不那么重要了？大部分时候，只要别写出一个死循环就行了。但当你拥有了强悍的硬件，是不是意味着烂代码也不是什么大问题？

Pavel Zaichenkov 11 票

我特别喜欢《算法导论（Introduction to Algorithms）》一书中的一个例子，以摧枯拉朽地方法说明了算法性能的重要性：

我们来比较两种排序算法：「插入排序」和 「归并排序」。他们的算法复杂度分别是 O(n2)=c1n2 和 O(nlogn)=c2n lg n。一般情况下，归并排序算法有一个更大的常数因子，所以我们假设 c1 < c 2。 为了回答你的问题，我们在一台时髦的高速电脑 A 上跑「插入排序」算法，和一台跑「归并排序」算法的老土电脑 B 做对比。 我们假设： - 输入的问题数据量为 1,000万个数字：n=107; - 电脑 A 一秒钟可以执行 1010 次运算指令 ( ~ 10GHz ); - 电脑 B 一秒钟只能执行 107 次运算指令 （ ~ 10MHz ); - 常数系数 C1 = 2 （有点夸张），C2 = 50 （比现实中稍微小了一点） 于是在以上假设下，我们得到如下结果： 牛X电脑A: 2·(107)2 次运算1010 次运算/秒=2·104 秒 给IE爪机用户：

土鳖电脑 B ：

50·107lg107 次运算107 次运算/秒≈1163 秒

给IE爪机蛋友：

所以你看，那部慢了1000倍的电脑，干活速度是快的那台的17倍。而且在现实中，归并算法有更高的效率，特别是随计算量增加的而更加明显。我希望这个答案能回答你的问题。

然而，这还不光是算法复杂程度的问题。在今天，单单想通过提高CPU主频来获得很明显的性能提升是不可能的。我们需要改良算法在多核CPU架构下的表现。而且这是个不太好对付的问题，因为随着内核数量的增加，其他方面的开销正在成为性能的障碍（比如内存访问调度控制）。所以，堆硬件很难获得线性的性能增长。

总而言之，当下对于算法的改进和以前一样重要，因为再多的CPU内核和再高的主频都无法给你带来和算法改进一样的回报。

Yuval Filmus 11票

总结一下，对于大数据处理、人工智能领域、分布式计算来说，算法的改进是不可或缺的；CPU 的运算能力在脱缰野马一般增长的需求面前，因为各种原因没有得到有效的利用，算法的重要性离死还远着呢。