算法：O、Ω、o、ω、Θ含义——数学定义

说明：① $N$ ：自然数 ② $c$ ：大于0的常数 ③ $n_{0}$ ：某一特定的自然数常数

1、O定义（上界）

设 $f$ 和 $g$ 都是定义域 $n$ $\in$ $N$ 的函数，记作 $f(n)$ 和 $g(n)$ 。若 $\exists$ $c > 0$ , $n_{0}>0$ $\Rightarrow$ $\forall$ $n \geq n_{0}$ ;都有如下： $0 \leq f(n) \leq c*g(n)$ 成立。则 $f(n)$ 渐进的上界是 $g(n)$ ,记作： $f(n)=O(g(n))$

2、Ω定义（下界）

设 $f$ 和 $g$ 都是定义域 $n \in N$ 的函数，记作 $f(n)$ 和 $g(n)$ 。若 $\exists$ $c > 0$ , $n_{0} > 0$ $\Rightarrow$ $\forall$ $n \geq n_{0}$ ;都有如下： $0 \leq c*g(n) \leq f(n)$ 成立。则 $f(n)$ 渐进的下界是 $g(n)$ ,记作： $f(n)=\Omega (g(n))$

3、o定义

设 $f$ 和 $g$ 都是定义域 $n \in N$ 的函数，记作 $f(n)$ 和 $g(n)$ 。若 $\forall$ $c > 0$ , $\exists$ $n_{0} > 0$ $\Rightarrow$ $\forall n \geq n_{0}$ ;都有如下： $0 \leq f(n) < c*g(n)$ 成立。则可以记作： $f(n)=o(g(n))$

4、ω定义

设 $f$ 和 $g$ 都是定义域 $n \in N$ 的函数，记作 $f(n)$ 和 $g(n)$ 。若 $\forall$ $c > 0$ ， $\exists$ $n_{0} > 0$ $\Rightarrow$ $\forall n \geq n_{0}$ ;都有如下： $0 \leq c*g(n) <f(n)$ 成立。则可以记作： $f(n)=\omega (g(n))$

5、Θ定义

若 $f(n)=O(g(n))$ 且 $f(n)=\Omega (g(n))$ ,则可以记作： $f(n)=\Theta (g(n))$ 。说明了 $f(n)$ 和 $g(n)$ 同阶。