算法(4th ed)(157):基础——算法分析 6.3.6

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

算法(4th ed)(157):基础——算法分析 6.3.6

(数学模型:总结)

对于大多数程序,得到其运行时间的数学模型所需的步骤如下:

  • 确定输入模型,定义问题的规模;
  • 识别内循环
  • 根据内循环中的操作确定成本模型
  • 对于给定的输入,判断这些操作的执行频率。这可能需要进行数学分析——我们在本书中会在学习具体的算法时给出一些例子。

如果一个程序含有多个方法,我们一般会分别讨论它们,例如我们在 1.1 节中见过的示例程序 BinarySearch。

二分查找。它的输入模型是大小为 N 的数组 a[]内循环是一个 while 循环中的所有语句,成本模型是比较操作(比较两个数组元素的值)。3.1 节中的命题 B 详细完整地给出了 1.1 节中讨论的内容,该命题说明它所需的比较次数最多为 lgN+1

白名单。它的输入模型是白名单的大小 N 和由标准输入得到的 M 个整数,且我们假设 M>>N内循环是一个 while 循环中的所有语句,成本模型是比较操作(承自二分查找)。由二分查找的分析我们可以立即得到对白名单问题的分析——比较次数最多为 M(lgN+1)

根据以下因素我们可以知道,白名单问题计算所需时间的增长数量级最多为 MlgN

  • 如果 N 很小,输入—输出可能会成为主要成本。
  • 比较的次数取决于输入——在 MMlgN 之间,取决于标准输入中有多少个整数在白名单中以及二分查找需要多久才能找出它们(一般来说为 MlgN)。
  • 我们假设 Arrays.sort() 的成本远小于 MlgNArrays.sort() 使用的是 2.2 节中的归并排序算法。我们会看到归并排序的运行时间的增长数量级为 NlogN(请见第 2 章的命题 G),因此这个假设是合理的。

因此,该模型支持了我们在 1.1 节中作出的假设,即当 MN 很大时二分查找算法也能够完成计算。如果我们将标准输入流的长度加倍,可以预计的是运行时间也将加倍;如果我们将白名单的大小加倍,可以预计的是运行时间只会稍有增加。

在算法分析中进行数学建模是一个多产的研究领域,但它多少超出了本书的范畴。通过二分查找、归并排序和其他许多算法你仍会看到,理解特定的数学模型对于理解基础算法的运行效率是很关键的,因此我们常常会详细地证明它们或是引用经典研究中的结论。在其中,我们会遇到各种数学分析中广泛使用的函数和近似函数。作为参考,我们分别在表 1.4.5 和表 1.4.6 中对它们的部分信息进行了总结。

表 1.4.5 算法分析中的常见函数

描述 记号 定义
向下取整(floor) x 不大于 x 的最大整数
向上取整(ceiling) x 不小于 x 的最小整数
自然对数 lnN logeN(ex=N)
以 2 为底的对数 lgN log2N(2x=N)
以 2 为底的整型对数 lgN 不大于 lgN 的最大整数 (N 的二进制表示的位数数)-1
调和级数 HN 1+1/2+1/3+1/4++1/N
阶乘 N! 1×2×3×4××N

表 1.4.6 算法分析中常用的近似函数

描述 近似函数
调和级数求和 HN=1+1/2+1/3+1/4++1/NlnN
等差数列求和 1+2+3+4++NN2/2
等比数列求和 1+2+4+8++N=2N12N,其中 N=2n
斯特灵公式 lgN!=lg1+lg2+lg3+lg4++lgNNlgN
二项式系数 (N\k)Nk/k!,其中 k 为小常数
指数函数 (11/x)x1/e

评论

发布