算法分析

Question

我正在阅读关于算法分析的主题。以下是书中的文本片段：

当n加倍时，线性程序的运行时间增加了2倍，二次程序增加了4倍，立方程式增加了8倍。在对数时间内运行的程序仅需要增加一个加法常数，而在O(n log n)内运行的程序在相同情况下需要花费略微超过两倍的时间。

如果低阶项具有相对较大的系数且n不够大，则这些增长可能很难发现。

我的问题是作者所说的低阶项具有相对较大的系数是什么意思？可以举个例子解释一下吗？

谢谢！

- venkysmarty

Answer 1

假设你的算法在处理n个元素时实际上执行了n^2+1000n次计算。现在，当n=1时，你需要进行1001次计算，当n=2时，你需要进行2004次计算。与线性增长相比，二次项的贡献微不足道，几乎无法察觉！然而，在渐近意义下，你的算法需要O(n^2)步，因此随着n的增大，将输入大小加倍会导致运行时间增加四倍。但是对于我们这个小值，从1加倍到2并没有使运行时间增加四倍！低阶项是n，其系数（1000）与领头项的系数n^2（为1）相比要大得多。这表明，渐近复杂度并不能说明特定的、尤其是小的值。它仅仅是一个关于n趋近于无穷大时行为的极限描述。

- Kerrek SB

---

我认为你的意思是：当n=2时，你需要2004（n^2 + 1000 n）。 - LiKao

@LiKao：谢谢，我做了！我正在修复...或许n^2 + 1000会是一个更好的例子。 - Kerrek SB

Answer 2

在使用O符号时，您需要指定函数中最大项作为性能上限。例如，如果性能始终由f = c₃n³ + c₂n² + c₁n + c₀限制，您将说它是O(n³)。作者的意思是当n很小时，系数可能比n对性能有更大的影响，例如，如果c₂非常大而c₃非常小，则性能可能看起来像是O(n²)，直到n的大小支配了系数，如果只根据特定小实例的相对性能进行判断。

- tvanfosson

Answer 3

渐近符号是指随着 n-> 无穷大时运行时间的界限。因此，一个 O(n log n) 的函数可能实际运行时间为 .1*n log n + 100000*n。

在这种情况下，100000*n项是“低阶项”。随着 n-> 无穷大，这一项被 .1*n log n 项所支配。

然而，正如你所看到的，对于小的 n，100000*n 项将主导运行时间。

- Patrick

Answer 4

例如，如果您在较小规模上拥有O(n)算法，则可能会出现T(n) = 490239n +（插入荒谬的常数），这意味着性能看起来很差，但随着规模的增加，您会发现增加始终是线性的。

真实世界的例子是归并排序，O(n logn)问题是递归具有计算成本或开销，这是n的因素，比nlogn的次序小，因此在大O中被丢弃，问题是该因素也变得相当大，并影响性能。

- Jesus Ramos