渐进复杂度

O 定义

公式

$$\mathcal{O}(g(n)) = \{f(n) : 0 \le f(n) \le cg(n) \; \forall \; n \ge n_0\}$$

Ω 定义

公式

$$\Omega(g(n)) = \{f(n) : 0 \le cg(n) \le f(n) \; \forall \; n \ge n_0\}$$

Θ 定义

公式

$$\Theta(g(n)) = \{f(n) : 0 \le c_1g(n) \le f(n) \le c_2g(n) \; \forall \; n \ge n_0\}$$

o 定义

公式

$$\mathcal{o}(g(n)) = \{f(n) : \forall c \; \exists \; n_0 > 0 \;, \;0 \le f(n) < cg(n) \; \forall \; n \ge n_0\}$$

即

$$\lim_{n\to\infty}\frac{f(n)}{g(n)} = 0$$

ω 定义

公式

$$\omega(g(n)) = \{f(n) : \forall c \; \exists \; n_0 > 0 \;, \;0 \le cg(n) < f(n) \; \forall \; n \ge n_0\}$$

即

$$\lim_{n\to\infty}\frac{f(n)}{g(n)} = \infty$$