差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
| public:cs:algorithm:clrs [2019/06/20 23:18] – 创建 oakfire | public:cs:algorithm:clrs [2019/08/20 12:00] (当前版本) – [3.1 渐近记号] oakfire | ||
|---|---|---|---|
| 行 24: | 行 24: | ||
| ==== 3.1 渐近记号 ==== | ==== 3.1 渐近记号 ==== | ||
| * 渐近紧确界(asymptotically tight bound) | * 渐近紧确界(asymptotically tight bound) | ||
| - | * \(\Theta(g(n))\) 表示以下函数的集合 | + | * \(\Theta(g(n))\) 表示以下函数的**集合** |
| - | * \(\Theta(g(n)) := \{f(n): \exists c_1 \exists c_2 \exists n_0( \forall n\geqslant n_0 \Rightarrow 0 \leqslant c_1 g(n) \leqslant f(n) \leqslant c_2 g(n)) \}\) | + | * \(\Theta(g(n)) := \{\;f(n): \exists c_1 \exists c_2 \exists n_0(\; \forall n\geqslant n_0 \Rightarrow 0 \leqslant c_1 g(n) \leqslant f(n) \leqslant c_2 g(n) \;) \;\}\) |
| - | * \(\Theta\) 记号渐近地给出一个函数的上界与下界 | + | * \(\Theta\) 记号渐近地给出一个函数的**上界**与**下界** |
| * 对任意多项式 \( p(n)=\sum_{i=0}^d a_i n^i \) 可证 \( p(n)=\Theta(n^d) \) | * 对任意多项式 \( p(n)=\sum_{i=0}^d a_i n^i \) 可证 \( p(n)=\Theta(n^d) \) | ||
| - | * 当只推渐近上界时，使用 \(O\) 记号 | + | * 当只推**渐近上界**时，使用 \(O\) 记号 |
| - | * \(O(g(n)) := \{ f(n): \exists c \exists n_0 ( \forall n\geqslant n_0 \Rightarrow 0 \leqslant f(n) \leqslant c g(n) ) \} \) | + | * \(O(g(n)) := \{\; f(n): \exists c \exists n_0 (\; \forall n\geqslant n_0 \Rightarrow 0 \leqslant f(n) \leqslant c g(n) \;) \;\} \) |
| - | * 显然 \(Theta(g(n)) \subseteq O(g(n)) \) | + | * 显然 \(\Theta(g(n)) \subseteq O(g(n)) \) |
| - | * 相应得，\(\Omega\) 记号只推一个函数的渐近下界 | + | * 相应得，\(\Omega\) 记号只推一个函数的**渐近下界** |
| - | * \(\Omega(g(n)) := \{ f(n): \exists c \exists n_0 ( \forall n\geqslant n_0 \Rightarrow 0 \leqslant c g(n) \leqslant f(n) ) \} \) | + | * \(\Omega(g(n)) := \{\;f(n): \exists c \exists n_0 (\; \forall n\geqslant n_0 \Rightarrow 0 \leqslant c g(n) \leqslant f(n) \;) \;\} \) |
| + | * **定理**3.1 对任意两个函数 \( f(n)\) 与 \( g(n) \), 有 \[ f(n)=\Theta(g(n)) \iff f(n)=O(g(n)) \land f(n)=\Omega(g(n)) \] | ||
| + | * \( o \) 记号表示非紧确上界 | ||
| + | * \( \omega \) 记号表示非紧确下界 | ||
| + | * 渐近比较的关系性质，假定 \(f(n)\) 和 \(g(n)\) 渐近为正 | ||
| + | * 传递性: \(f(n)=\Theta(g(n)) \land g(n)=\Theta(h(n)) \; | ||
| + | * 自反性: \(f(n)=\Theta(f(n))\) | ||
| + | * 对称性: \(f(n)=\Theta(g(n)) \iff g(n)=\Theta(f(n))\) | ||
| + | * 转置对称性 : \(f(n)=O(g(n)) \iff g(n)=\Omega(f(n))\) | ||
oakfire