5.1. 更快的计算机，还是更快的算法？¶

设想你有一个待求解的问题，并且你已知一个算法，其运行时间与 \(n^2\) 成正比，其中 \(n\) 是输入规模的度量。 不幸的是，由此得到的程序运行时间比可接受的时间长十倍。 如果把现有计算机换成一台快十倍的新机器，这个 \(n^2\) 算法会变得可以接受吗？ 如果问题规模保持不变，那么即使算法的增长率很高，更快的计算机或许也能让你足够快地完成工作。 但大多数换上更快计算机的人都会遇到一件有趣的事：他们并不是更快地运行同样的问题，而是运行一个更大的问题！ 比方说，在旧计算机上你满足于对 10,000 条记录排序，因为计算机可以在你午餐休息期间完成这项工作。 而在新计算机上，你可能希望在同样的时间内对 100,000 条记录排序。 你并不会提早从午餐回来，所以解决一个更大的问题对你更有利。 而且由于新机器快了十倍，你会希望对多十倍的记录排序。

如果算法的增长率是线性的（即如果描述输入规模为 \(n\) 时运行时间的方程是 \(\mathbf{T}(n) = cn\)，其中 \(c\) 为某个常数），那么新机器对 100,000 条记录排序所需的时间，与旧机器对 10,000 条记录排序所需的时间相同。 如果算法的增长率大于 \(cn\)，比如 \(c_1n^2\)，那么在一台快十倍的机器上，你将 无法 在同样的时间内完成规模大十倍的问题。

用更快的计算机，在给定时间内能解决规模多大的问题？ 假设新机器比旧机器快十倍。 设旧机器能在一小时内解决规模为 \(n\) 的问题，那么新机器一小时内能解决的最大问题是什么？ 下表给出了在两台机器上、对应五种运行时间函数分别能解决多大的问题。

这张表说明了许多重要的问题。 前两个方程都是线性的，改变的只是常数因子的值。 在这两种情形下，快十倍的机器都使问题规模增大十倍。 换句话说，虽然常数的值确实会影响固定时间内所能解决的问题的绝对规模，但它并不影响更快的计算机所带来的问题规模的 改进 （相对于原始规模的比例）。 无论算法的增长率如何，这一关系都成立：常数因子绝不会影响更快的计算机所带来的相对改进。

时间方程为 \(\mathbf{T}(n) = 2n^2\) 的算法，从更快的机器那里获得的改进远不及增长率呈线性的算法。 改进不是十倍，而只有十的平方根，即 \(\sqrt{10} \approx 3.16\) 。 因此，增长率更高的算法不仅在给定时间内原本就只能解决更小的问题，而且 也 只能从更快的计算机那里获得较少的加速。 随着计算机越来越快，问题规模之间的差距也越拉越大。

增长率为 \(\mathbf{T}(n) = 5 n \log n\) 的算法，其改进幅度大于二次增长率的算法，但不及增长率呈线性的各种算法。

注意，运行时间呈指数级增长的算法会出现某种特别的情况。 如果在图上画出它的曲线可以看到，随着 \(n\) 的增长，运行时间与 \(2^n\) 成正比的算法的曲线上升得非常快。 在快十倍的机器上，问题规模约变为 \(n + 3\) ，准确地说，是 \(n + \log_2 10\) 。 对于增长率呈指数级的算法，问题规模的增大是通过加上一个常数实现的，而不是乘以一个倍数。 由于 \(n\) 的旧值是 13，新的问题规模就是 16。 如果明年你再买一台又快十倍的计算机，那么这台新计算机（比最初的计算机快 100 倍）也只能运行规模为 19 的问题。 如果你还有第二个程序，其增长率为 \(2^n\)，并且最初的计算机能在一小时内运行规模为 1000 的问题，那么快十倍的机器一小时内也只能运行规模为 1003 的问题！ 因此，指数增长率与表中所列的其他增长率有着本质上的不同。 这一差异的重要意义，是 computational complexity theory 中的一个重要主题。

与其购买更快的计算机，不如考虑一下：如果把运行时间与 \(n^2\) 成正比的算法，换成运行时间与 \(n \log n\) 成正比的新算法，会发生什么。 在把增长率函数与输入规模联系起来的图中，固定的时间量会表现为一条水平线。 如果表示解决你的问题可用时间的那条线，位于所讨论的两条增长率曲线的交点之上，那么运行时间增长较慢的算法更快。 运行时间为 \(\mathbf{T}n=n^2\) 的算法，对规模为 \(n=1024\) 的输入需要 \(1024 \times 1024 = 1,048,576\) 个时间步。 运行时间为 \(\mathbf{T}(n) = n \log n\) 的算法，对规模为 \(n = 1024\) 的输入只需要 \(1024 \times 10 = 10,240\) 个时间步，与运行时间为 \(\mathbf{T}(n) = n^2\) 的算法相比，改进远超十倍。 由于只要 \(n > 58\)，就有 \(n^2 > 10 n \log n\)，因此对本例而言，如果典型的问题规模大于 58，那么更换算法要比购买一台快十倍的计算机划算得多。 此外，当你确实要购买更快的计算机时，增长率较低的算法也能带来更大的好处，使新计算机在一定时间内能够运行规模更大的问题。