函数的渐近的界&阶的比较

一、函数的渐近的界

我们在研究算法性能的时候，往往会在意算法的运行时间，而运行时间又与算法输入的规模相关，对于一个算法，我们可以求出运行时间和输入规模的函数，当输入规模足够大时，站在极限的角度看，就可以求出运行时间如何随着输入规模的无限增长而增长。
这种令输入规模无限大而研究运行时间增长情况的做法，就是在研究算法的渐近效率。

几种符号的直观理解：

Θ,O,Ω的图像表示

Θ（渐近紧确界）：若 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 ))时，有：

二、几个重要结论（阶的比较）

基本函数类：

至少指数级： $2^n,3^n,n!,...$
多项式级： $n,n^2,nlogn,n^{1over2},...$
对数多项式级： $logn,log^2n,loglogn,...$
多项式函数<指数函数： $n^d = o(r^n),r>1,d>0$
对数函数<幂函数： $ln n = o(n^d),d>0$

对数函数：

(1) $log_2n=Θ(log_tn)$ （换底）
(2) $log_bn=o(n^α)$ (α>0)
(3) $a^{log_bn}=n^{lob_ba}$ （即，形如指数函数的幂是log级，则可化成多项式级）

指数函数与阶乘：

Stirling公式: $n!=sqrt{2πn}({nover e})^n(1+Θ({1over n}))$
$n!=o(n^n)$
$n!=ω(2^n)$
$log(n!)=Θ(nlogn)$

作者：楠子小先生
链接：https://www.jianshu.com/p/b9e4126e5bce
来源：简书
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。