有关函数渐近的界的定理

作者: 背负代码的宇智波 | 来源:发表于2018-12-31 21:39 被阅读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)).

小结

• 估计函数的阶的方法：

计算极限阶具有传递性

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

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

网友评论

本文标题：有关函数渐近的界的定理

本文链接：https://www.haomeiwen.com/subject/bdgwlqtx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！