可能重复:
Big O的简单英文解释
我需要弄清楚O(n)以下内容:
f(n) = 10n^2 + 10n + 20
我能想到的只是50,而且我太尴尬了,不知道我是怎么想出来的.
有人可以解释它意味着什么以及我应该如何计算它f(n)？
Big-O表示法与复杂性分析有关.一个功能是O(g(n)),如果(对于所有除了一些n值)它是上界通过一些常数倍数g(n)作为n趋于无穷大.更正式的:
f(n)是O(g(n))当且仅当存在常数n0,并c使得对所有n >= n0,f(n) <= c.g(n)
在这种情况下,f(n) = 10n^2 + 10n + 20,所以f(n)是O(n^2),O(n^3),O(n^4),等.严格的上限是O(n^2).
用外行人的话说,这意味着f(n)增长不会比平方更差,因为n趋于无穷大.
有一个相应的Big-Omega表示法,它可以用于类似方式的下界函数.在这种情况下,f(n)也是Omega(n^2):也就是说,它的增长并不比平方增长更n倾向于无穷大.
最后,还有一个Big-Theta符号,其结合了这两种,即当且仅当f(n)在O(g(n))与f(n)处于Omega(g(n))然后f(n)是Theta(g(n)).在这种情况下,f(n)它在Theta(n^2):即,它n倾向于无穷大地完全呈二次方增长.
- >所有这一点的重点是,随着n变大,线性(10n)和常数(20)项基本上变得无关紧要,因为函数的值受二次项的影响更大.< -