为什么我们忽略大O表示法中的系数?
在寻找与“ BigO”表示法有关的答案时,我看到了许多SO答案,但我仍然不清楚一些要点。
为什么我们忽略系数?
例如这个答案说的最终复杂度2N + 2
是O(N)
; 我们也删除了前导2
系数和最终常数2
。
删除2
也许可以理解的最终常量。毕竟,这N
可能非常大,因此“忘记”决赛2
可能只会改变总数的一小部分。
但是,我无法清楚地理解消除 领先的 系数不会产生什么影响。如果2
上方的前导变为a 1
或a 3
,则总计的百分比变化将很大。
同样,显然2N^3 + 99N^2 + 500
是O(N^3)
。我们如何忽略99N^2
与500
?
回答:
Big-O表示法的目的是找出值趋于无穷大时函数渐近行为的主导因素是什么。
当我们遍历功能域时,某些因素变得比其他因素更重要。
想象一下f(n) = n^3+n^2
。至于n
趋于无穷大,n^2
相对于使用越来越少有关n^3
。
但这仅仅是定义的直觉。实际上,由于形式上的定义,我们忽略了函数的某些部分:
f(x) = O(g(x))
如x->infinity
当且仅当存在正实数
M
和x_0
诸如
|f(x)| <= M|g(x)|
为了所有x > x_0
。
那是在维基百科上。实际的意思是在一个点(之后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
。
以上是 为什么我们忽略大O表示法中的系数? 的全部内容, 来源链接: utcz.com/qa/412692.html