算法分析

Question

我正在阅读算法分析的主题。这是书中的文字片段

当n倍时，运行时间增加2倍于线性规划，4倍于二次规划，8倍于三次规划。在对数时间运行的程序在n倍时只需要一个加性常数，而在O(n log )中运行的程序在相同情况下运行所需时间略多于两倍。

如果低阶项的系数相对较大，且n还不够大，则很难发现这些增加。

我的问题是，作者的意思是，低阶项的系数相对较大？有人能用例子解释吗？

谢谢!

Answer 1

假设您的算法在运行n^2 + 1000 n元素时实际执行n计算。现在，对于n = 1，您需要1001计算，对于n = 2，您需要2004年。与线性增长的差别很小，你几乎找不到二次贡献！

但是，在渐近情况下，您的算法需要O(n^2)步骤，所以渐近地(当n变大)使输入的大小翻倍于运行时的四倍。但是对于我们的小值，翻倍从1到2并没有使运行时翻两番！低阶项为n，其系数(1000)大于前级项n^2( 1)的系数。

这表明，渐近复杂性并没有说明任何关于特定的，特别是小值。随着n变得越来越大，这仅仅是对这种行为的一种限制。

Answer 2

渐近表示法是指运行时的界为n->无穷大.因此，一个函数O(n log )可能具有.1*n log n+ 100000*n的实际运行时。

在这种情况下，100000*n项是“低阶项”.由于n->无穷大，这一项被.1*n log n项压倒.

但是，正如您所看到的，对于小n，100000*n项将主导运行时。

Answer 3

例如，如果在较低的尺度上有一个O(n)算法，那么T(n) = 490239n +(在这里插入荒谬常数)，这意味着性能看起来会很糟糕，但是随着尺度的增加，你会看到增长总是线性的。

现实世界中的例子是合并排序，O(n logn)问题是递归有一个计算成本或开销，它是n的一个因子，它比nlogn小，所以它在大O中被丢弃，问题是这个因素变得相当大，影响性能。