算法分析
我正在阅读算法分析主题。 这是本书的文本片段
当n加倍时，线性程序的运行时间增加2倍，二次程序的运行时间增加4倍，立方程序的运行时间增加8倍。 在对数时间内运行的程序在n加倍时只能使用一个加法常量，而在O（n log n）中运行的程序所用时间略长于两倍，以便在相同情况下运行。
如果低阶项具有相对较大的系数且n不够大，这些增加可能难以发现。
我的问题是作者意味着低阶项具有相对较大的系数？ 有没有人可以用例子来解释
谢谢！
当使用O符号时，可以指定该函数的最大项，这是您的性能界限。 例如，如果性能总是受到f = c3n3 + c2n2 + c1n + c0的约束，那么你会说这是O（n3）。 作者指出，当n很小时，系数可能会对性能产生比n更大的影响，例如如果c2非常大且c3非常小，则性能可能看起来是O（n2），直到n如果你只是通过n的特定小实例的相对性能来支配这些系数，那么它就支配了系数。
假设你的算法在n元素上运行时实际执行n^2 + 1000 n计算。 现在，对于n = 1您需要1001次计算，对于n = 2您需要2004年。与线性增长的差别很小，您几乎不能发现二次方贡献！
然而，渐近地，您的算法需要O（n ^ 2）个步骤，所以渐近地（如n变大）将输入大小加倍，使您的运行时间增加四倍。 但是对于我们的小值，从1倍增加到2倍并没有使运行时增加四倍！ 低阶项是n ，其系数（1000）与前导项n^2 （它是1）的系数相比较大。
这显示了渐近复杂性如何不说特别的东西，特别是小的值。 这只是一个关于n变大的行为的限制性陈述。
渐近表示法指的是运行时间的界限为n->无穷大。 因此，函数O（n log n）的实际运行时间可能为.1 * n log n + 100000 * n。
在这种情况下，100000 * n项是“低阶项”。 由于n - >无穷大，这个术语被.1 * n log n项所压制。
但是，正如你所看到的，对于小的n，100000 * n将主宰运行时。
链接地址: http://www.djcxy.com/p/40063.html