算法(4th ed)(153):基础——算法分析 6.3.2

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

算法(4th ed)(153):基础——算法分析 6.3.2

(数学模型:近似运行时间)

按照 Knuth 的方法,要得到一个 Java 程序的总运行时间的数学表达式,(原则上)我们需要研究我们的 Java 编译器来找出每条 Java 指令所对应的机器指令数,并根据我们的计算机的指令规范得到每条机器指令的运行时间,然后才能得到一个总运行时间。对于 ThreeSum,这个时间的大致总结如表 1.4.4 所示。我们根据执行的频率将 Java 的语句分块,计算出每种频率的首项近似,判定每条指令的执行成本并计算出总和。请注意,某些执行频率可能会依赖于输入。在本例中,cnt++ 的执行次数显然就是依赖于输入的——它就是和为 0 的整数三元组的数量,范围在 0 到 N3/6 之间。通过用常数 t0t1t2…表示各个代码块的执行时间,我们假设每个 Java 代码块所对应的机器指令集所需的执行时间都是固定的。除此之外,我们基本不会涉及任何特定系统的细节(这些常数的值)。从这里我们观察到的一个关键现象是执行最频繁的指令决定了程序执行的总时间——我们将这些指令称为程序的内循环。对于 ThreeSum 来说,它的内循环是将 k1、判断它是否小于 N 以及判断给定的三个整数之和是否为 0 的语句(也许还包括记数的语句,不过这取决于输入)。这种情况是很典型的:许多程序的运行时间都只取决于其中的一小部分指令。

评论

发布