算法(4th ed)(155):基础——算法分析 6.3.4

阅读数:25 2019 年 11 月 6 日 07:53

算法(4th ed)(155):基础——算法分析 6.3.4

(数学模型:算法的分析)

类似于性质 A 的猜想的意义很重要,因为它们将抽象世界中的一个 Java 程序和真实世界中运行它的一台计算机联系了起来。增长数量级概念的应用使我们能够继续向前迈进一步:将程序和它实现的算法隔离开来。ThreeSum 的运行时间的增长数量级是 N3,这与它是由 Java 实现或是它运行在你的笔记本电脑上或是某人的手机上或是一台超级计算机上无关。决定这一点的主要因素是它需要检查输入中任意三个整数的所有可能组合。你所使用的算法(有时还要算上输入模型)决定了增长的数量级。将算法和某台计算机上的具体实现分离开来是一个强大的概念,因为这使我们对算法性能的知识可以应用于任何计算机。例如,我们可以说 ThreeSum 是暴力算法“计算所有不同的整数三元组的和,统计和为 0 的组数”的一种实现,可以预料的是在任何计算机上使用任何语言对该算法的实现所需的运行时间都是和 N3 成正比的。实际上,经典算法的性能理论大部分都发表于数十年前,但它们仍然适用于今天的计算机。

评论

发布