文章目录

• 一、渐进上界
• 二、大 O 记号
• 三、常用的渐进上界

一、渐进上界

---

$\mathrm{g}(\mathrm{n})$ 是 $\mathrm{f}(\mathrm{n})$ 的渐进上界 :

存在 $\mathrm{c}$ , 并且存在 $\mathrm{N}$ , 使得任何 $\mathrm{n}$ , 并且 $\mathrm{n}\ge \mathrm{N}$ , 则有 $\mathrm{f}(\mathrm{n})\le \mathrm{c}\mathrm{g}(\mathrm{n})$ ,

则称 $\mathrm{g}(\mathrm{n})$ 是 $\mathrm{f}(\mathrm{n})$ 的渐进上界 ;

符号化表示 :

$\exists \mathrm{c}>0\exists \mathrm{N}\forall \mathrm{n}(\mathrm{n}\ge \mathrm{N}\Rightarrow \mathrm{f}(\mathrm{n})\le \mathrm{c}\mathrm{g}(\mathrm{n}))$

存在 $\mathrm{N}$ , 使得任何 $\mathrm{n}$ 并且 $\mathrm{n}\ge \mathrm{N}$ ,

$\exists N\forall n(n\ge N)$

上述表述 , 表示 当 $\mathrm{n}$ 充分大 ;

$\exists \mathrm{N}\forall \mathrm{n}(\mathrm{n}\ge \mathrm{N}\Rightarrow \mathrm{f}(\mathrm{n})\le \mathrm{c}\mathrm{g}(\mathrm{n}))$ 整体的含义如下 ,

尽管 $\mathrm{f}(\mathrm{n})$ 不一定小于等于 $\mathrm{c}\mathrm{g}(\mathrm{n})$ , 当 $\mathrm{n}$ 充分大时 , 一定有 $\mathrm{f}(\mathrm{n})\le \mathrm{c}\mathrm{g}(\mathrm{n})$ , 这是一个趋势 ,

称 $\mathrm{g}(\mathrm{n})$ 是 $\mathrm{f}(\mathrm{n})$ 的渐进上界 ;

在渐近分析中 , 常数 $\mathrm{c}$ 一般忽略不计 , 其大小是 $2,3$ 或者几亿 都不重要 ;

二、大 O 记号

---

$\mathrm{f}(\mathrm{n})=\mathrm{O}(\mathrm{g}(\mathrm{n}))$

三、常用的渐进上界

---

多项式上界 : ${\mathrm{n}}^{\mathrm{c}}$ , 如 :

① ${\mathrm{n}}^2=\mathrm{O}({\mathrm{n}}^2)$

② $3{\mathrm{n}}^2+2\mathrm{n}+1=\mathrm{O}({\mathrm{n}}^2)$ , 忽略低阶项 , 系数项 ;

③ $4{\mathrm{n}}^3+2{\mathrm{n}}^2+\mathrm{n}+3=\mathrm{O}({\mathrm{n}}^3)$ , 忽略低阶项 , 系数项 ;

指数级上界 : $2^{{\mathrm{n}}^{\mathrm{c}}}$ , 如 :

① $\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{n}=\mathrm{O}({\mathrm{n}}^{\mathrm{x}})(\mathrm{x}>0)$

大 $\mathrm{O}$ 记号运算 :

$\mathrm{O}(\mathrm{n})+\mathrm{O}({\mathrm{n}}^2)=\mathrm{O}({\mathrm{n}}^2)$ , 忽略低阶项 ;

渐进上界表示符号会 忽略系数影响 , 忽略低阶的项 ;

总结

以上是生活随笔为你收集整理的【计算理论】计算复杂性 ( 算法复杂度标记 | 渐进上界 | 大 O 记号 | 常用的渐进上界 )的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。