差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
| public:cs:algorithm:clrs [2019/06/20 23:21] – oakfire | public:cs:algorithm:clrs [2019/08/20 12:00] (当前版本) – [3.1 渐近记号] oakfire | ||
|---|---|---|---|
| 行 30: | 行 30: | ||
| * 当只推**渐近上界**时，使用 O 记号 | * 当只推**渐近上界**时，使用 O 记号 | ||
| * O(g(n)):={f(n):∃c∃n0(∀n⩾n0⇒0⩽f(n)⩽cg(n))} | * O(g(n)):={f(n):∃c∃n0(∀n⩾n0⇒0⩽f(n)⩽cg(n))} | ||
| - | * 显然 Theta(g(n))⊆O(g(n)) | + | * 显然 \(\Theta(g(n)) \subseteq O(g(n)) \) |
| * 相应得，Ω 记号只推一个函数的**渐近下界** | * 相应得，Ω 记号只推一个函数的**渐近下界** | ||
| * Ω(g(n)):={f(n):∃c∃n0(∀n⩾n0⇒0⩽cg(n)⩽f(n))} | * Ω(g(n)):={f(n):∃c∃n0(∀n⩾n0⇒0⩽cg(n)⩽f(n))} | ||
| + | * **定理**3.1 对任意两个函数 f(n) 与 g(n), 有 f(n)=Θ(g(n))⟺f(n)=O(g(n))∧f(n)=Ω(g(n)) | ||
| + | * o 记号表示非紧确上界 | ||
| + | * ω 记号表示非紧确下界 | ||
| + | * 渐近比较的关系性质，假定 f(n) 和 g(n) 渐近为正 | ||
| + | * 传递性: f(n)=Θ(g(n))∧g(n)=Θ(h(n))⟹f(n)=Θ(h(n)) | ||
| + | * 自反性: f(n)=Θ(f(n)) | ||
| + | * 对称性: f(n)=Θ(g(n))⟺g(n)=Θ(f(n)) | ||
| + | * 转置对称性 : f(n)=O(g(n))⟺g(n)=Ω(f(n)) | ||
oakfire