函数的渐近的界&阶的比较
发布网友
发布时间：2024-05-28 11:41
共1个回答
热心网友
时间：2024-05-29 06:56
我们在研究算法性能的时候，往往会在意算法的运行时间，而运行时间又与算法输入的规模相关，对于一个算法，我们可以求出运行时间和输入规模的函数，当输入规模足够大时，站在极限的角度看，就可以求出运行时间如何随着输入规模的无限增长而增长。
这种令输入规模无限大 而研究运行时间增长情况的做法，就是在研究算法的 渐近 效率。
Θ（渐近紧确界）： 若 f ( n ) = Θ ( g ( n ))，则存在 c1>0 ，c2 >0，s.t. n→∞时， f ( n )夹在 c1 g ( n )和 c2 g ( n )之间。即g(n)既是f(n)的渐近上界又是渐近下界，可假装理解为 ”f(n) = g(n)“
且当 f ( n ) = Θ ( g ( n ))时，有：
O （渐近上界）： 若f ( n ) = O ( g ( n ))，则 存在 c>0, s.t. n→∞时，f(n)在cg(n)下面。即g(n)是f(n)的渐近上界，可假装理解为 “f(n) <= g(n)” 。
o （非渐近紧确上界）： 与O的区别是， 任意 c>0, 都使f(n)在cg(n)下面。是非紧的上界，可假装理解为 “f(n) < g(n)” 。
且当f ( n ) = o ( g ( n ))时，有：
Ω （渐近上界）： 若f ( n ) = Ω ( g ( n ))，则 存在 c>0, s.t. n→∞时，f(n)在cg(n)上面。即g(n)是f(n)的渐近下界，可假装理解为 “f(n) >= g(n)” 。
ω （非渐近紧确下界）： 与Ω的区别是， 任意 c>0, 都使f(n)在cg(n)上面。是非紧的下界，可假装理解为 “f(n) > g(n)” 。
且当f ( n ) = ω ( g ( n ))时，有：
至少指数级：
多项式级：
对数多项式级：
多项式函数<指数函数：
对数函数<幂函数：
(1) （换底）
(2) (α>0)
(3) （即，形如指数函数的幂是log级，则可化成多项式级）
Stirling公式:
