算法分析 : In practice, 高阶项的系数重要吗？

Question

考虑 an^2 + bn + c。我知道对于大的 n，bn 和 c 变得微不足道。

我还了解到，对于较大的 n，2n^2 和 n^2 之间的差异非常微不足道 n^2 和 n*log(n) 之间的区别。

不过，2n^2和n^2还是相差2阶。这在实践中重要吗？或者人们只是考虑没有系数的算法？为什么？

Answer 1

如果您对时序感兴趣，则实际系数很重要。但 big-O 实际上与时间无关，它与可扩展性有关。当您看到一个描述为 O(n^2) 的算法时，您并不知道在特定计算机上使用特定编译器以特定语言解决大小为 n 的问题需要多长时间，但您知道大小为 2n 的问题大约需要 4 倍的时间。

可以忽略系数的原因是，如果考虑不同规模问题的比率，低阶项的系数渐近占优，而最高阶项的系数在比率中抵消。