算法(4th ed)(156):基础——算法分析 6.3.5

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

算法(4th ed)(156):基础——算法分析 6.3.5

(数学模型:成本模型)

我们使用了一个成本模型来评估算法的性质。这个模型定义了我们所研究的算法中的基本操作。例如,适合于右侧所示的 3-sum 问题的成本模型是我们访问数组元素的次数。

3-sum 的成本模型。在研究解决 3-sum 问题的算法时,我们记录的是数组的访问次数(访问数组元素的次数,无论读写)。

在这个成本模型之下,我们可以用精确的数学语言说明算法而非某个特定实现的性质,如下:

命题 B。3-sum 的暴力算法使用了 N3/2 次数组访问来计算 N 个整数中和为 0 的整数三元组的数量。
证明。该算法访问了 N3/6 个整数三元组中的所有 3 个整数。

我们使用术语命题来表示在某个成本模型下算法的数学性质。在全书中我们都会使用某个确定的成本模型研究所讨论的算法。我们希望通过明确成本模型使给定实现所需的运行时间的增长数量级和它背后的算法的成本的增长数量级相同(换句话说,成本模型应该和内循环中的操作相关)。我们会研究算法准确的数学性质(命题)并对实现的性能作出猜想(性质),可以通过实验验证这些猜想。在本例中,命题 B 的数学结论支持了性质 A 中由科学方法得到并由实验验证过的猜想。

评论

发布