差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
| public:cs:algorithm:clrs [2019/06/20 23:46] – oakfire | public:cs:algorithm:clrs [2019/08/20 12:00] (当前版本) – [3.1 渐近记号] oakfire | ||
|---|---|---|---|
| 行 30: | 行 30: | ||
| * 当只推**渐近上界**时，使用 \(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) \;) \;\} \) | ||
oakfire