O notation mean?
Possible Duplicate:
Plain English explanation of Big O
I need to figure out O(n) of the following:
f(n) = 10n^2 + 10n + 20
All I can come up with is 50 , and I am just too embarrassed to state how I came up with that.
Can someone explain what it means and how I should calculate it for f(n) above?
Big-O notation is to do with complexity analysis. A function is O(g(n)) if (for all except some n values) it is upper-bounded by some constant multiple of g(n) as n tends to infinity. More formally:
f(n) is in O(g(n)) iff there exist constants n0 and c such that for all n >= n0 , f(n) <= cg(n)
In this case, f(n) = 10n^2 + 10n + 20 , so f(n) is in O(n^2) , O(n^3) , O(n^4) , etc. The tightest upper bound is O(n^2) .
In layman's terms, what this means is that f(n) grows no worse than quadratically as n tends to infinity.
There's a corresponding Big-Omega notation which can be used to lower-bound functions in a similar manner. In this case, f(n) is also Omega(n^2) : that is, it grows no better than quadratically as n tends to infinity.
Finally, there's a Big-Theta notation which combines the two, ie iff f(n) is in O(g(n)) and f(n) is in Omega(g(n)) then f(n) is in Theta(g(n)) . In this case, f(n) is in Theta(n^2) : that is, it grows exactly quadratically as n tends to infinity.
--> The point of all this is that as n gets big, the linear ( 10n ) and constant ( 20 ) terms become essentially irrelevant, as the value of the function is far more affected by the quadratic term. <--
上一篇: 增加复杂程度的列表？
下一篇: O符号是什么意思？