算法(4th ed)(180):基础——算法分析 6.7.7

阅读数:5 2019 年 11 月 9 日 15:38

算法(4th ed)(180):基础——算法分析 6.7.7

(注意事项:多个问题参量)

我们过去的重点一直是使用仅需要一个参量的函数来衡量程序的性能,参量一般是命令行参数或是输入的规模。但是,多个参量也是可能的。典型的例子是需要构造一个数据结构并使用该数据结构进行一系列操作的算法。在这种应用程序中数据结构的大小和操作的次数都是问题的参量。我们已经见过一个这样的例子,即对使用二分查找的白名单问题的分析,其中白名单中有 N 个整数而输入中有 M 个整数,运行时间一般和 MlogN 成正比。

尽管需要注意的问题很多,对于每个程序员来说,对程序的运行时间的增长数量级的理解都是非常有价值的,而且我们这里所描述的方法也都十分强大并且应用范围广泛。Knuth 证明了原则上我们只要正确并完整地使用了这些方法就能够对程序作出详细准确的预测。计算机系统一般都非常复杂,完整精确的分析最好留给专家们,但相同的方法也可以有效地近似估计出任何程序所需的运行时间。火箭科学家需要大致知道一枚试验火箭的着陆地点是在大海里还是在城市中;医学研究者需要知道一次药物测试是会杀死还是治愈实验对象;任何使用计算机程序的科学家或是工程师也应该能够预计它是会运行一秒钟还是一年。

评论

发布