Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1095120
  • 博文数量: 242
  • 博客积分: 10209
  • 博客等级: 上将
  • 技术积分: 3028
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-12 09:27
文章分类

全部博文(242)

文章存档

2014年(1)

2013年(1)

2010年(51)

2009年(65)

2008年(124)

我的朋友

分类:

2008-04-15 16:33:23

   
   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) |
给主人留下些什么吧!~~