算法(4th ed)(147):基础——算法分析 6.2

阅读数:8 2019 年 11 月 6 日 07:42

算法(4th ed)(147):基础——算法分析 6.2

(观察)

我们的第一个挑战是决定如何定量测量程序的运行时间。在这里这个任务比自然科学中的要简单得多。我们不需要向火星发射火箭或者牺牲一些实验室的小动物或是分裂某个原子——只需要运行程序即可。事实上,每次运行程序都是在进行一次科学实验,将这个程序和自然世界联系起来并回答我们的一个核心问题:我的程序会运行多长时间?

我们对大多数程序的第一个定量观察就是计算性任务的困难程度可以用问题的规模来衡量。一般来说,问题的规模可以是输入的大小或是某个命令行参数的值。根据直觉,程序的运行时间应该随着问题规模的增长而变长,但我们每次在开发和运行一个程序时想问的问题都是运行时间的增长有多快。

从许多程序中得到的另一个定量观察是运行时间和输入本身相对无关,它主要取决于问题规模。如果这个关系不成立,我们就需要进行一些实验来更好地理解并更好地控制运行时间对输入的敏感度。但这个关系常常是成立的,因此我们现在来重点研究如何更好地将问题规模和运行时间的关系量化。

评论

发布