渐近紧确界(asymptotically tight bound)
\(\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\) 记号渐近地给出一个函数的上界与下界
对任意多项式 \( p(n)=\sum_{i=0}^d a_i n^i \) 可证 \( p(n)=\Theta(n^d) \)
当只推渐近上界时，使用 \(O\) 记号
相应得，\(\Omega\) 记号只推一个函数的渐近下界
定理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))\)