1.4 算法分析
Robert Sedgewick Kevin Wayne
随着使用计算机的经验的增长,人们在使用计算机解决困难问题或是处理大量数据时不可避免的将会产生这样的疑问:
我的程序会运行多长时间?
为什么我的程序耗尽了所有内存?
在重建某个音乐或照片库、安装某个新应用程序、编辑某个大型文档或是处理一大批实验数据时,你肯定也问过自己这些问题。这些问题太模糊了,我们无法准确回答——答案取决于许多因素,比如你所使用的计算机的性能、被处理的数据的性质和完成任务所使用的程序(实现了某种算法)。这些因素都会产生大量需要分析的信息。
尽管有这些困难,你在本节中将会看到,为这些基础问题给出实质性的答案有时其实非常简单。这个过程的基础是科学方法,它是科学家们为获取自然界知识所使用的一系列为大家所认同的方法。我们将会使用数学分析为算法成本建立简洁的模型并使用实验数据验证这些模型。
1.4.1 科学方法
科学家用来理解自然世界的方法对于研究计算机程序的运行时间同样有效:
细致地观察真实世界的特点,通常还要有精确的测量;
根据观察结果提出假设模型;
根据模型预测未来的事件;
继续观察并核实预测的准确性;
如此反复直到确认预测和观察一致。
科学方法的一条关键原则是我们所设计的实验必须是可重现的,这样他人也可以自己验证假设的真实性。所有的假设也必须是可证伪的,这样我们才能确认某个假设是错误的(并需要修正)。正如爱因斯坦的一句名言所说:“再多的实验也不一定能够证明我是对的,但只需要一个实验就能证明我是错的。”我们永远也没法知道某个假设是否绝对正确,我们只能验证它和我们的观察的一致性。
1.4.2 观察
我们的第一个挑战是决定如何定量测量程序的运行时间。在这里这个任务比自然科学中的要简单得多。我们不需要向火星发射火箭或者牺牲一些实验室的小动物或是分裂某个原子——只需要运行程序即可。事实上,每次运行程序都是在进行一次科学实验,将这个程序和自然世界联系起来并回答我们的一个核心问题:我的程序会运行多长时间?
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文介绍了算法分析的重要性以及科学方法在计算机程序运行时间分析中的应用。文章指出,随着计算机使用经验的增长,人们在解决困难问题或处理大量数据时常常会关心程序的运行时间和内存消耗情况。为了回答这些问题,科学方法被引入到算法分析中,包括观察、假设、预测和核实等步骤。文章还介绍了如何通过数学分析和实验数据验证模型来建立算法成本的简洁模型。在观察方面,文章提到了如何定量测量程序的运行时间,以及程序的运行时间与问题规模的关系。通过一个示例程序的运行时间记录,读者可以了解到如何使用计时器来测量程序的运行时间。文章内容丰富,涉及到算法分析的重要性、科学方法在程序运行时间分析中的应用以及数学模型的建立和简化方法,对于想要深入了解算法分析的读者具有很高的参考价值。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《算法(第 4 版)》
《算法(第 4 版)》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示,欢迎踊跃留言。
收起评论