算法(4th ed)(154):基础——算法分析 6.3.3

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

算法(4th ed)(154):基础——算法分析 6.3.3

(数学模型:对增长数量级的猜想)

总之,1.4.2.3 节中的实验和表 1.4.4 中的数学模型都支持以下猜想:

性质 A。ThreeSum(在 N 个数中找出三个和为 0 的整数元组的数量)的运行时间的增长数量级为 N3
例证。设 T(N) 为 ThreeSum 处理 N 个整数的运行时间。根据前文所述的数学模型有 [T(N)aN3,其中常数 a 取决于计算机的具体型号。在许多计算机上完成的实验(包括你我的计算机)都验证了这个近似。

在本书中,我们使用性质表示需要用实验验证的猜想。数学分析的最终结果和我们的实验分析的最终结果完全相同——ThreeSum 的运行时间是 aN3,其中常数 a 取决于计算机的具体型号。这次吻合既验证了实验结果和数学模型,也揭示了该程序的更多性质,因为我们不需要实验就能确定 N 的指数。稍加努力,我们就能确定某个特定系统上的 a 的值,不过这一般都只在有性能压力的情形下才需要由专家来完成。

算法(4th ed)(154):基础——算法分析 6.3.3

图 1.4.4 程序语句执行频率的分析

表 1.4.4 程序运行时间的分析(示例)

语句块 运行时间(以秒记) 频率 总时间
E t0 x(取决于输入) t0x
D t1 N3/6N2/2+N/3 t1(N3/6N2/2+N/3)
C t2 N2/2N/2 t2(N2/2N/2)
B t3 N t3N
A t4 1 t4
总时间 算法(4th ed)(154):基础——算法分析 6.3.3
近似 (t1/6)N3(假设 x 很小)
增长的数量级 N3

评论

发布