有关函数渐近的界的定理

2018-12-31  本文已影响0人  背负代码的宇智波

定理1

定理 设 f 和 g是定义域为自然数集合的函数.

(1)如果 \lim_{x\to∞} f(n)/g(n)存在, 并且等于某个常数c>0, 那么 f(n) = \Theta (g(n)).

(2)如果\lim_{x\to∞} f(n)/g(n) =0，那么f(n) = o(g(n)).

(3)如果 \lim_{x\to∞} f(n)/g(n)=+∞，那么f(n) = ω(g(n)).

证明用到\Theta ,\omicron ,\omega 定义

证明定理1(1)

根据极限定义，对于给定正数 ε 存在某个n_{0} ，

只要n ≥ n_{0} ，就有

| f(n)/g(n)-c | < ε

c -ε < f(n)/g(n) < c +ε

c/2 < f(n)/g(n) < 3c/2 < 2c

对所有n≥n_{0} , f(n)≤ 2cg(n), 于是 f(n)=O(g(n))；

取ε =c/2,

对所有n≥n_{0} , f(n)≥(c/2)g(n),于是 f(n)=Ω(g(n)).

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

例：估计函数的阶

例1 设 f (n) = \frac{1}{2} b^2-3n , 证明 f(n) = \Theta (n^2 ).

证 因为\lim_{x\to∞} \frac{f(n)}{n^2 } =\lim_{x\to∞} \frac{\frac{1}{2} n^2-3n}{n^2 }=\frac{1}{2}

根据定理1，有f(n) = \Theta (n^2 )

一些重要结果

可证明：多项式函数的阶低于指数函数的阶

n^d=\omicron (r^n ),r>1,d>0

证 不妨设d为正整数

分子分母求导数

\lim_{x\to∞} \frac{n^d }{r^n } =\lim_{x\to∞} \frac{dn^{d-1} }{r^n (\ln r) }=\lim_{x\to∞} \frac{d(d-1)n^{d-2} }{r^n (\ln r)^2 }=...=lim_{x\to∞} \frac{d! }{r^n (\ln r)^d }=0

定理 2

定理 设函数f, g, h的定义域为自然数集合，

(1) 如果 f=O(g) 且 g=O(h)，那么 f=O(h).

(2)如果 f=Ω(g) 且 g=Ω(h)， 那么 f =Ω (h).

(3)如果 f=\Theta (g) 和 g=\Theta (h)， 那么 f =\Theta (h).

函数的阶之间的关系具有传递性

例子

按照阶从高到低排序以下函数：

f(n) =(n^2+n)/2,g(n)=10n

h(n)=1.5^n,t(n)=n^{1/2}

h(n) = ω(f(n))，

f(n) = ω(g(n)),

g(n) = ω(t(n)),

排序h(n),f(n),g(n),t(n)

定理3

定理 假设函数f 和g的定义域为自然数集，

若对某个其它函数h, 有 f =O(h) 和 g=O(h)，

那么f + g = O(h).该性质可以推广到有限个函数.算法由有限步骤构成. 若每一步的时间复杂度函数的上界都是h(n)，那么该算法的时间复杂度函数可以写作O(h(n)).

小结

• 估计函数的阶的方法：

计算极限阶具有传递性

• 对数函数的阶低于幂函数的阶，多项式函数的阶低于指数函数的阶

• 算法的时间复杂度是各步操作时间之和，在常数步的情况下取最高阶的函数即可

上一篇下一篇

猜你喜欢

热点阅读