public:cs:algorithm:clrs

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版		 前一修订版
public:cs:algorithm:clrs [2019/06/20 23:28] – oakfirepublic: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) \;) \;\} \)
-  * 定理3.1 对任意两个函数 \( f(n)\) 与 \( g(n) \), 有 \[ f(n)=\Theta(g(n)) \iff f(n)=O(g(n)) \land f(n)=\Omega(g(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)) \;\Longrightarrow\; f(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))\)
  
  
  • public/cs/algorithm/clrs.1561044502.txt.gz
  • 最后更改: 2019/06/20 23:28
  • 由 oakfire