算法(4th ed)(151):基础——算法分析 6.3

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

算法(4th ed)(151):基础——算法分析 6.3

(数学模型)

在计算机科学的早期,D. E. Knuth 认为,尽管有许多复杂的因素影响着我们对程序的运行时间的理解,原则上我们仍然可能构造出一个数学模型来描述任意程序的运行时间。Knuth 的基本见地很简单——一个程序运行的总时间主要和两点有关:

  • 执行每条语句的耗时;
  • 执行每条语句的频率。

前者取决于计算机、Java 编译器和操作系统,后者取决于程序本身和输入。如果对于程序的所有部分我们都知道了这些性质,可以将它们相乘并将程序中所有指令的成本相加得到总运行时间。第一个挑战是判定语句的执行频率。有些语句的分析很容易:例如,ThreeSum.count() 中将 cnt 的值设为 0 的语句只会执行一次。有些则需要深入分析:例如,ThreeSum.count() 中的 if 语句会执行 N(N1)(N2)/6 次(从输入数组中能够取得的三个不同整数的数量——请见练习 1.4.1)。其他则取决于输入数据,例如,ThreeSum.count() 中的指令 cnt++ 执行的次数为输入中和为 0 的整数三元组的数量,这可能是 0 也可能是任意值。对于 DoublingTest 的情况,输入值是随机产生的,我们可以用概率分析得到该值的期望(请见练习 1.4.40)。

评论

发布