$\Theta$ - 渐近紧确界记号，既是上界也是下界，等于的意思(tight)
Definition 1.1: 设 $f(n)$ 和 $g(n)$ 是定义域为自然数集合的函数。如果 $\lim _{n \rightarrow \infty} \frac{f(n)}{g(n)}$ 存在, 并且等于某个常数 $c(c>0)$, 那么 $f(n)=$ $\Theta(g(n))$ 。通俗理解为 $f(n)$ 和 $g(n)$ 同阶, $\Theta$ 用来表示算法的精确阶。
Definition 1.2: 存在常数 $c_1 、 c_2$ 和 $n_0$, 使得对所有 $n \geq n_0$, 有 $0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n)$, 即若存在常数 $c_1 、 c_2$, 使得对于足够大的 n , 函数 $f(n)$ 能 “夹入” $c_1 g(n)$ 与 $c_2 g(n)$ 之间, 则 $f(n)$ 属于集合 $\Theta(g(n))$, 记作 $f(n) \in \Theta(g(n))$。作为代替, 我们通常记 “ $f(n)=\Theta(g(n))$ “。
$O$ - 渐近上界记号，表示上界，小于等于的意思(tightness unknown)
Definition 2: 设 $f(n)$ 和 $g(n)$ 是定义域为自然数集 $N$ 上的函数。若存在正数 $c$ 和 $n_0$, 使得对一切 $n \geq n_0$ 都有 $0 \leq f(n) \leq c g(n)$ 成立,则称 $f(n)$ 的渐进的上界是 $g(n)$, 记作 $f(n)=O(g(n))$ 。通俗的说n满足一定条件范围内, 函数 $f(n)$ 的阶不高于函数 $g(n)$ 。
$o$ - 非渐近紧确上界，表示上界，小于的意思(not tight)
Definition 3.1: 设 $f(n)$ 和 $g(n)$ 是定义域为自然数集 $N$ 上的函数。若对于任意正数 $c$ ，都存在 $n_0$, 使得对一切 $n \geq n_0$ 都有 $0 \leq$ $f(n)<c g(n)$ 成立, 则称 $f(n)$ 的渐进的非紧确上界是 $g(n)$, 记作 $f(n)=o(g(n))$ 。通俗的说 $n$ 满足一定条件范围内, 函数 $f(n)$ 的阶低于函数 $g(n)$ 。
Definition 3.2: 设 $f(n)$ 和 $g(n)$ 是定义域为自然数集合的函数。如果 $\lim _{n \rightarrow \infty} \frac{f(n)}{g(n)}=0$, 那么 $f(n)=o(g(n))$ 。通俗理解为 $f(n)$ 低于 $g(n)$ 的阶。
$\Omega$ - 渐进下界记号，表示下界，大于等于的意思(tightness unknown)
Definition 4: 设 $f(n)$ 和 $g(n)$ 是定义域为自然数集 $N$ 上的函数。若存在正数 $c$ 和 $n_0$, 使得对一切 $n \geq n_0$ 都有 $0 \leq c g(n) \leq f(n)$ 成立,则称 $f(n)$ 的渐进的下界是 $g(n)$, 记作 $f(n)=\Omega(g(n))$ 。通俗的说 $n$ 满足一定条件范围内, 函数 $f(n)$ 的阶不低于函数 $g(n)$ 。
$\omega$ - 非渐近紧确下界，表示下界，大于的意思(not tight)
Definition 5.1: 设 $f(n)$ 和 $g(n)$ 是定义域为自然数集 $N$ 上的函数。若对于任意正数 $c$, 都存在 $n_0$, 使得对一切 $n \geq n_0$ 都有 $0 \leq$ $c g(n)<f(n)$ 成立, 则称 $f(n)$ 的渐进的非紧确下界是 $g(n)$, 记作 $f(n)=\omega(g(n))$ 。通俗的说 $n$ 满足一定条件范围内, 函数 $f(n)$ 的阶高于函数 $g(n)$ 。
Definition 5.2: 设 $f(n)$ 和 $g(n)$ 是定义域为自然数集合的函数。如果 $\lim _{n \rightarrow \infty} \frac{f(n)}{g(n)}=\infty$ ，那么 $f(n)=o(g(n))$ 。通俗理解为 $f(n)$ 高于 $g(n)$ 的阶。
总结
| 记号 | 含义 | 通俗理解 |
|---|---|---|
| $\Theta$（西塔） | 紧确界。 | 相当于”=” |
| $O$ （大欧） | 上界。 | 相当于”<=” |
| $o$（小欧） | 非紧的上界。 | 相当于”<” |
| $\Omega$（大欧米伽） | 下界。 | 相当于”>=” |
| $\omega$（小欧米伽） | 非紧的下界。 | 相当于”>” |