算法(4th ed)(194):基础——算法分析 6.11

阅读数:5 2019 年 11 月 9 日 15:44

算法(4th ed)(194):基础——算法分析 6.11

(答疑)

 为什么不用 StdRandom 生成随机数来代替 1Mints.txt ?

 在开发中,这样做能够使调试代码和重复实验更简单。每次调用 StdRandom 都会产生不同的值,所以修正一个 bug 之后并再次运行程序可能并不能测试这次修正!可以使用 StdRandom 中的 setSeed() 方法来解决这个问题,但 1Mints.txt 类参考文件能够使添加测试用例变得更容易。另外,不同的程序员还能够比较程序在不同计算机上的性能而不必担心输入模型的不同。只要你的程序已经调试完毕且你已经大致了解了它的性能,当然有必要用随机数据测试它。例如,DoublingTest 和 DoublingRatio 使用的就是这种方式。

 我在计算机上运行了 DoublingRatio,但我得到的结果和书上的不一致。有些比例的收敛值并不是 8,为什么?

 这就是为什么我们在 1.4.7 节中讨论了注意事项。最可能的情况是你计算机上的操作系统在实验进行中还开小差去干了点儿别的活儿。消除这种问题的一种方式是花更多时间做更多次实验。比如,可以修改 DoublingTest,让它对于每个 N 都进行 1000 次实验,这样对于每个 N 它都能给出对运行时间更加精确的估计值。

 在近似函数的定义中,“随着 N 的增大”确切的意思是什么?

 f(N)g(N) 的正式定义为 limNf(N)/g(N)=1

 我还见到过其他表示增长的数量级的符号,它们都表示什么意思?

 使用最广泛的记法是“大 O”:对于 f(N)g(N),如果存在常数 c 和 N0 使得对于所有 N>N0 都有 |f(N)|<cg(N),则我们称 f(N)O(g(N))。这种记法在描述算法性能的渐进上限时十分有用,这在算法理论领域是十分重要的,但它在预测算法性能或是比较算法时并没有什么作用。

 上题中,为什么说没有作用呢?

 主要原因是它描述的仅仅是运行时间的上限,而算法的实际性能可能要好得多。一个算法的运行时间可能既是 O(N2) 也是 aNlogN 的。因此,它不能解释类似倍率实验等测试(请见 1.4.6 节命题 C)。

 那为什么“大 O”符号的应用非常广泛呢?

 因为它简化了对增长数量级的上限的研究,甚至也适用于一些无法进行精确分析的复杂算法。另外,它还可以和计算理论中用于将算法按照它们在最坏情况下的性能分类的“大 Omega”和“大 Theta”符号一起使用。如果存在常数 c 和 N0 使得对于 N>N0 都有 |f(N)|>cg(N),则我们称 f(N)Ω(g(N))。如果 f(N) 既是 O(g(N)) 也是 Ω(g(N)),则我们称 f(N)Θ(g(N))。“大 Omega”记法通常用来表示最坏情况下的性能下限,而“大 Theta”记法则通常用于描述算法的最优性能,即不存在有更好的最坏情况下的渐进增长数量级的算法。算法的最优性显然是实际应用中值得考虑的一点,但你会看到,还有其他许多因素需要考虑。

 渐进性能的上限难道不重要吗?

 重要,但我们希望讨论的是给定成本模型下所有语句执行的准确频率,因为它们能够提供更多关于算法性能的信息,而且从我们所讨论的算法中获取这些频率是可能的。例如,我们可以说“ThreeSum 访问数组的次数为 N3/2”,以及“在最坏情况下 cnt++ 执行的次数为 N3/6”,它们虽然有些冗长但给出的信息比“ThreeSum 的运行时间为 O(N3)”要多得多。

 当一个算法的运行时间的增长数量级为 NlogN 时,根据双倍测试会得到它的运行时间为 aN 的猜想(其中 a 为常数)。这有问题吗?

 需要注意的是,我们不能根据实验数据推测它们所符合的某个特定的数学模型。但如果我们只是在预测性能,这并不是什么问题。例如,当 N 在 16 000 到 32 000 之间时,14NNlgN 的图像非常接近。这些数据同时与两条曲线吻合。随着 N 的增大,两条曲线更为接近。想要用实验来检验一个算法的运行时间是线性对数级别而非线性级别是要费一番工夫的。

 int[] a = new int[N] 表示 N 次数组访问吗(所有数组元素均会被初始化为 0)?

 大多数情况下是的,我们在本书中也是这样假设的,不过复杂编译器的实现会在遇到大型稀疏数组时尽力避免这种开销。

评论

发布