复杂度¶
记号¶
| 记号 | \(O\) | \(\Omega\) | \(\Theta\) | \(o\) | \(\omega\) |
|---|---|---|---|---|---|
| 对应关系 | \(\leqslant\) | \(\geqslant\) | \(\approx\) | \(<\) | \(>\) |
大 O 符号¶
\(O\) 为 忽略常数的渐进复杂度上界 记号
| 符号 | 名称 | 符号 | 名称 |
|---|---|---|---|
| \(O(1)\) | 常数阶 | \(O(n\log n)\) | 对数阶 |
| \(O(\log n)\) | 对数阶 | \(O(n^2)\) | 平方阶 |
| \(O(\log^cn)\) | 多对数阶 | \(O(n^c)\) | 多项式阶 |
| \(O(n)\) | 线性阶 | \(O(c^n)\) | 指数阶 |
| \(O(n\log^* n)\) | 迭代对数阶 | \(O(n!)\) | 阶乘阶 |
\[
f(n)=O[\,g(n)\,]\Leftrightarrow f(n)\leqslant g(n)
\]
\[
f(n)+g(n)=O[\,s(n)+r(n)\,]
\]
\[
f(n)\cdot g(n)=O[\,s(n)\cdot r(n)\,]
\]
递推关系¶
对给定的递推关系
\[
T(g(n))=E(T(n),n)
\]
证明
\[
T(n)=O(f(n))
\]
的一般步骤如下：
-
检查归纳基础
\[ T[\,g(1)\,]\leqslant E[\,T(1),1\,] \]是否成立
-
将以待证式为归纳假设，证明
\[ f[\,g(n)\,]\geqslant E[\,f(n),n\,] \]最后需要证明的式子，实际上就是把 原递推式中 \(T\) 换成 \(f\) 后改成不等号 得到的
要特别注意不等号的方向，