Let f (n) and g(n) be functions from positive integers to positive reals. We say
f = O(g) (which means that “f grows no faster than g”) if there is a constant c > 0
such that f (n) ≤ c · g(n).
Just as O(·) is an analog of ≤, we can also define analogs of ≥ and = as follows:
f = Ω(g) means g = O(f )
f = Θ(g) means f = O(g) and f = Ω(g).
Here are some commonsense rules that help simplify functions by omitting dominated terms:
1. Multiplicative constants can be omitted: 14n^2 becomes n^2 .
2. n^a dominates n^b if a > b: for instance, n^2 dominates n.
3. Any exponential dominates any polynomial: 3^n dominates n^5 (it even dominates 2^n ).
4. Likewise, any polynomial dominates any logarithm: n dominates (log n)^3 . This also means, for example, that n^2 dominates nlogn.
阅读(1509) | 评论(0) | 转发(0) |