algorithm - 为什么我们忽略大 O 表示法中的系数？

Question

在搜索与“Big O”符号相关的答案时，我看到了很多 SO 答案，例如 this , this , 或 this , 但我仍然没有清楚地理解一些要点。

为什么我们忽略系数？

例如this answer表示 2N + 2 的最终复杂度是 O(N)；我们也删除了前导系数 2 和最终常数 2。

删除 2 的最终常量也许可以理解。毕竟，N 可能非常大，因此“忘记”最后的 2 可能只会将总计改变一小部分。

但是我无法清楚地理解移除leading 系数并没有什么不同。如果上面的前导 2 变成 1 或 3，则总计的百分比变化会很大。

类似地，2N^3 + 99N^2 + 500 显然是 O(N^3)。我们如何忽略 99N^2 和 500？

Answer 1

Big-O 表示法的目的是找出在函数的值趋于无穷时渐近行为中的主导因素。

当我们遍历功能域时，一些因素变得比其他因素更重要。

想象 f(n) = n^3+n^2 .作为n去无穷大，n^2与 n^3 相比变得越来越不相关.

但这只是定义背后的直觉。实际上，由于正式定义，我们忽略了函数的某些部分:

f(x) = O(g(x)) as x->infinity

if and only if there is a positive real M and a real x_0 such as

|f(x)| <= M|g(x)| for all x > x_0.

那是 in wikipedia .这实际上意味着有一个点(在 x_0 之后)之后是 g(x) 的某个倍数。主宰f(x) .该定义就像是 f(x) 值的松散上限.

从中我们可以推导出许多其他属性，例如 f(x)+K = O(f(x)) , f(x^n+x^n-1)=O(x^n)等。这只是使用定义来证明这些的问题。

特别，移除系数 ( K*f(x) = O(f(x)) ) 背后的直觉在于我们试图用计算复杂性来衡量的东西。归根结底，一切都与时间(或任何资源有关)有关。但是很难知道每个操作需要多少时间。一种算法可以执行 2n运营及其他n ，但后者可能有一个与之相关的大常数时间。因此，为此目的，很难推断出 n 之间的区别。和 2n .