等阶估计

定义

已知

  • 函数 $f$ 和函数 $g$

则 $f\in \Theta(g)$ :=

  • $f\in O(g) \land f \in \Omega(g)$ 或
  • $\lim_{ n \to \infty } \frac{f}{g} = \mathrm{const} \ (\neq 0 \land < \infty)$