<分区>
Possible Duplicate:
Plain English explanation of Big O
我需要找出以下的 O(n):
f(n) = 10n^2 + 10n + 20
我能想到的只有 50，我实在不好意思说出我是怎么想到的。
谁能解释一下它的含义以及我应该如何为上面的 f(n) 计算它？
<分区>
Possible Duplicate:
Plain English explanation of 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结合了两者的符号，即 iff f(n)在O(g(n))和 f(n)在Omega(g(n))然后 f(n)在Theta(g(n)) .在这种情况下，f(n)在Theta(n^2) :也就是说，它以 n 的二次方增长趋于无穷大。
--> 这一切的重点是 n变大时，线性 (10n) 和常量 (20) 项基本上变得无关紧要，因为函数值受二次项的影响更大。 <--
关于algorithm - 大 O 表示法是什么意思？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8073270/