算法导论笔记:渐近大于和多项式大于

 转自:http://stackess.leanote.com/post/5131774ba20f
在《算法导论》的第四章中用主方法求解递归式,没有说清渐近大于(小于)和多项式大于(小于)的概念,尤其是针对case 3举的例子令我困惑,在查阅了多种解释后,经验证并整理如下。

渐近大于(asymptotically larger)

渐近大于 ,记作

注意都是非渐近紧缺的界。
多项式大于(polynomially larger)

is polynomially bigger than when asymptotically dominates even after we multiply by a very small order polynomial (e.g., ).参考

多项式大于

存在常数,使得,即

例如
1. 只渐近大于,因为虽然,但对任意常数 ,
2. 非渐近大于,因为 ,即实际上是渐近紧确的界。
3. 多项式大于 ,因为存在常数,则
4. 多项式大于,因为存在常数,则

同理
渐近小于(asymptotically smaller)
渐近小于,也记作

多项式小于(polynomially smaller)
多项式小于

存在常数,使得,即

 

发表评论