文章目錄

• 一、漸進上界
• 二、大 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})$ 的漸進上界 ;

符號化表示 :

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

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

$?N?n(n\ge N)$

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

$?\mathrm{N}?\mathrm{n}(\mathrm{n}\ge \mathrm{N}?\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 记号 | 常用的渐进上界 )的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。