一、函数渐进的界

2018-11-15  本文已影响0人  静水流深不流浅

一、大O 符号（上界）

定义：设f和g是定义域为自然数集N上的函数。若存在正数c和n0,使得对一切n\geq n0有0\leq f(n)\leq cg(n)成立，则称f(n)的渐近的上界是g(n),记作f(n)=O(g(n))。例子：

        设f(n) = n\land 2 + n,则

        f(n)=O(  n\land 2  ),则c=2,n0=1即可

        f(n)=O(n\land 3),则c=1,n0=2即可

1.f(n)=O(g(n)),f(n)的阶不高于g(n)的阶。

2.可能存在多个正数c,只要指出一个即可。

3.对前面有限个值可以不满足不等式。

4.常函数可以写作O（1）

二、大\Omega 符号（下界）

定义：设f和g是定义域为自然数集N上的函数。若存在正数c和n0,使得对一切n\geq n0，0\leq cg(n)\leq f(n)成立，则称f(n)的渐近的下界是g(n),记作f(n)=\Omega (g(n))。例子：

       设f(n) = n\land 2 + n,则

       f(n)=\Omega (  n\land 2 )，则c=1,n0=1即可

       f(n)=\Omega ( 100n )，则c=1/100，n0=1即可

1.f(n) = \Omega (g(n)),f(n)的阶不低于g(n)的阶。

2.可能存在多个正数c,只要指出一个即可。

3.对前面有限个n值可以不满足不等式。

三、小o符号（上界）

定义:设f和g是定义域为自然数集N上的函数。若对于任意正数c都存在n0,使得对一切n\geq n0有0\leq f(n)<cg(n)成立，则记作f(n)=o(g(n))，例子：

            f(n)=n\land 2+n,则

            f(n)=o(n\land 3)

            c>=1显然成立，因为n\land 2+n<cn\land 3(n0=2)

            任给1>c>0,取n0>\lceil 2/c\rceil 即可。因为

            cn>=cn0>2  (当n>=n0)

            n\land 2+n<2n\land 2<cn\land 3

1.f(n) = o(g(n)),f(n)的阶低于g(n)的阶。

2.对不同正数c，n0不一样。c越小n0越大。

3.对前面有限个n值可以不满足不等式。 

四、小\omega 符号（下界）

定义:设f和g是定义域为自然数集N上的函数。若对于任意正数c都存在n0,使得对一切n\geq n0有0\leq cg(n)<f(n)成立，则记作f(n) =\omega (g(n))

            设f(n)=n\land 2+n,则

            f(n)=w(n),

            不能写f(n)=w(n\land 2),因为取c=2，不存在n0使得对一切n>=n0有下式成立

            cn\land 2=2n\land 2<n\land 2+n

1.f(n) = \omega (g(n)),f(n)的阶高于g(n)的阶。

2.对不同正数c，n0不一样。c越大n0越大。

3.对前面有限个n值可以不满足不等式。 

五、\Theta 符号

若f(n)=O(g(n))且f(n)=\Omega (g(n))，则记作

f（n）=\Theta (g(n))

例子： f(n)=n^2+n,g(n)=100n^2,那么有

            f(n)=\Theta (g(n))

1.f(n)的阶与g(n)的阶相等

2.对前面有限个n值可以不满足条件。

上一篇下一篇

猜你喜欢

热点阅读