logo头像

贾维斯的小屋

数据结构与算法——算法复杂度

渐进记号

一、五种渐进记号

  • 大$O$记号:

对于给定函数$g(n)$,$f(n)=O(g(n))$:存在正常量$c$和$n_{0}$,使得对所有$n \geq n_{0}$,有$0 \leq f(n) \leq cg(n)$成立。$f(n)$只有一个渐进上界,$f(n)$的阶不高于$g(n)$的阶。

  • $\Omega$记号:

对于给定函数$g(n)$,$f(n)=O(g(n))$:存在正常量$c$和$n_{0}$,使得对所有$n \geq n_{0}$,有$0 \leq cg(n) \leq f(n)$成立。$f(n)$只有一个渐进下界,$f(n)$的阶不低于$g(n)$的阶。

  • $\Theta$记号:

对于给定函数$g(n)$,$f(n)=\Theta(g(n))$:存在正常量$c_{1}$,$c_{2}$和$n_{0}$,使得对所有$n \geq n_{0}$,有$0 \leq c_{1}g(n) \leq f(n) \leq c_{2}g(n)$成立。$\Theta$记号渐进地给出了一个函数的上界和下界,$f(n)$的阶等于$g(n)$的阶

若$f(n)=O(g(n))$且$f(n)= \Omega (g(n))$,则$f(n)= \Theta (g(n))$。

  • 小$o$记号:

对于给定函数$g(n)$,$f(n)=O(g(n))$:存在正常量$c > 0$和$n_{0} > 0$,使得对所有$n \geq n_{0}$,有$0 \leq f(n) < cg(n)$成立。$f(n)$只有一个渐进紧确上界,$f(n)$的阶低于$g(n)$的阶。

  • $\omega$记号:

对于给定函数$g(n)$,$f(n)=O(g(n))$:存在正常量$c > 0$和$n_{0} > 0$,使得对所有$n \geq n_{0}$,有$0 \leq cg(n) < f(n)$成立。$f(n)$只有一个渐进紧确下界,$f(n)$的阶高于$g(n)$的阶。

二、 相关定理

  • 定理1:

(1)如果$\lim_{n \to +\infty} \frac{f(n)}{g(n)}$存在,且为某个常数$c$,则$f(n)= \Theta (g(n))$
(2)如果$\lim_{n \to +\infty} \frac{f(n)}{g(n)}=0$,则$f(n)= O (g(n))$
(3)如果$\lim_{n \to +\infty} \frac{f(n)}{g(n)}=\infty$,则$f(n)= \omega (g(n))$

由定理1可以导出两个重要结果:

(1)多项式函数的阶低于指数函数的阶:

(2)对数函数的阶低于幂函数的阶:

  • 定理2,传递性:

若$f(n)= \Theta (g(n))$,且$g(n)=\Theta (h(n))$,则$f(n)=\Theta(h(n))$。对于大$O$、小$o$、$\Omega$、$\omega$同样成立。

  • 定理3:

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

三、相关性质

  • 1、自反性:
  • 2、对称性:

$f(n)=\Theta(g(n))$,当且仅当$g(n)=\Theta(f(n))$

  • 3、转置对称性:

$f(n)=O(g(n))$当且仅当$g(n)=\Omega(f(n))$
$f(n)=o(g(n))$当且仅当$g(n)=\omega(f(n))$

四、几类重要函数

  • 至少指数函数级: $2^{n}$, $3^{n}$, $n!$, $2^{2^{n}}$, $n2^{n}$, $(\log n)^{\log n}=n^{\log \log n}$

  • 多项式级: $n$, $n^{2}$, $n {\rm log}n$, $n^{\frac{1}{2}}$, $n^{3}$, ${\rm log}(n!)=\Theta(n {\rm log}n)$

  • 对数多项式级: ${\rm log}n$, ${\rm log}^{2}n$, ${\rm log log}n$, $\sqrt{\log n}$


取整函数

  • $\lfloor x \rfloor$:向下取整,$\lceil x \rceil$:向上取整

  • 一些性质:


参考资料

微信打赏

赞赏是不耍流氓的鼓励