算法(4th ed)(193):基础——算法分析 6.10

阅读数:20 2019 年 11 月 9 日 15:44

算法(4th ed)(193):基础——算法分析 6.10

(展望)

良好的性能是非常重要的。速度极慢的程序和不正确的程序一样无用,因此显然有必要在一开始就关注程序的运行成本,这能够让你大致估计出所要解决的问题的规模,而聪明的做法是时刻关注程序中的内循环代码的组成。

但在编程领域中,最常见的错误或许就是过于关注程序的性能。你的首要任务应该是写出清晰正确的代码。仅仅为了提高运行速度而修改程序的事最好留给专家们来做。事实上,这么做常常会降低生产效率,因为它会产生复杂而难以理解的代码。C.A.R. Hoare(快速排序的发明人,也是一位推动编写清晰而正确的代码的领军人物)曾将这种想法总结为:“不成熟的优化是所有罪恶之源。”Knuth 为这句话加上了一个定语“在编程领域中(或者至少是大部分罪恶)”。另外,如果降低成本带来的效益并不明显,那么对运行时间的改进就不值得了。例如,如果一个程序所需的运行时间只是一瞬间而已,那么即使是将它的速度提高十倍也是无关紧要的。即使程序的运行需要好几分钟,实现并调试一个新算法所需要的时间也可能会大大超过直接运行一个稍微慢一点的算法——这种时候就应该让计算机代劳。更糟糕的情况是你可能花了大量的时间和心血去实现一个理论上能够改进程序的想法,但实际上什么也没发生。

在编程领域中,第二常见的错误或许是完全忽略了程序的性能。较快的算法一般都比暴力算法更复杂,所以很多人宁可使用较慢的算法也不愿应付复杂的代码。但是,几行优秀的代码有时能够给你带来巨大的收益。许多人在使用平方级别的暴力算法去解决问题的盲目等待中浪费了大量的时间,但实际上线性级别或是线性对数级别的算法能够在几分之一的时间内完成任务。当我们需要处理大规模问题时,通常,除了寻找更好的算法之外我们别无选择。

我们将使用本节所述的各种方法来评估算法对内存的使用,并在多个成本模型下对算法进行数学分析从而得到相应的近似函数,然后根据近似函数提出对算法所需的运行时间的增长数量级的猜想并通过实验验证它们。改进程序,使之更加清晰、高效和优雅应该是我们一贯的目标。如果你在开发一个程序的全过程中都能关注它的运行成本,那么你都会从该程序的每次执行中受益。

评论

发布