算法：渐进记号的含义及时间复杂度计算

本文主要是介绍算法：渐进记号的含义及时间复杂度计算，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

渐进记号及时间复杂度计算

渐近符号
- 渐近记号 $\Omega$
- 渐进记号 $\Theta$
- 渐进记号小 $\omicron$
- 渐进记号小 $\omega$
- 渐进记号大 $\Omicron$
- 常见的时间复杂度关系
时间复杂度计算：递归方程
- 代入法
- 迭代法
- 套用公式法

渐近符号

渐近记号 $\Omega$

$f(n)=\Omega(g(n))$ 当且仅当存在正的常数C和 $n_0$ ，使得对于所有的 $n≥ n_0$ ，有 $f (n) \geq C (g (n))$ 。此时，称 $g (n)$ 是 $f (n)$ 的下界。
根据符号 $\Omega$ 的定义，用它评估算法的复杂度得到的是问题规模充分大时的一个下界。这个下界的阶越高，评估越精确，越有价值。

例：设 $f(n)=n^2+n$ ,则
$f(n)=\Omega(n^2)$ ，取 $c=1,n_0=1$ 即可
$f(n)=\Omega(100n)$ ，取 $c=1/100,n_0=1$ 即可
显然， $\Omega(n^2)$ 作为下界更为精确。

渐进记号 $\Theta$

$f(n)=\Theta(g(n))$ 当且仅当存在正常数和 $C_1,C_2,n_0$ ，使得对于所有的 $n≥n_0$ , 有 $C_1(g(n))≤f(n)≤ C_2(g(n))$ 。此时，称 $f (n)$ 与 $g (n)$ 同阶。
这种渐进符号是指，当问题规模足够大的时候，算法的运行时间将主要取决于时间表达式的第一项，其它项的执行时间可以忽略不计。第一项的常数系数，随着n的增大，对算法的执行时间也变得不重要了。

例： $3 n + 2 = Θ (n)$
$10n^2+4n+2= Θ(n^2)$
$5×2^n+n^2= Θ(2^n)$

渐进记号小 $\omicron$

$f(n)=\omicron(g(n))$ 当且仅当 $f(n)=\omicron(g(n))$ 和 $g(n)\neq \omicron(f(n))$ ，此时， $g (n)$ 是 $f (n)$ 的一个绝对上界。
小 $\omicron$ 提供的上界可能是渐近紧确的，也可能是非紧确的。（如： $2n^2=\omicron(n^2)$ 是渐近紧确的，而 $2n=\omicron(n^2)$ 是非紧确上界。

例： $\omicron(n^2)$

渐进记号小 $\omega$

$f(n)=\omega(g(n))$ 当且仅当 $f(n)=\omega(g(n))$ 和 $g(n)\neq \omega(f(n))$ ，此时， $g (n)$ 是 $f (n)$ 的一个绝对下界。
$\omega$ 表示一个非渐进紧确的下界。

例： $f(n)=n^2+n$ ，则 $f (n) =$ \omega $(n)$ 是正确的， $f (n) =$ \omega $n^2)$ 是错误的。

渐进记号大 $\Omicron$

设 $f (n)$ 和 $g (n)$ 是定义域为自然数集上的函数。若存在正数 $c$ 和 $n_0$ c和n_0c，使得对一切 $n≥ n_0$ 都有 $0 \leq f (n) \leq c g (n)$ 成立，则称 $f (n)$ 的渐进的上界是 $g (n)$ ，记作 $f(n)=\Omicron g(n)$ 。
根据符号大 $\Omicron$ 的定义，用它评估算法的复杂度得到的只是问题规模充分大时的一个上界。这个上界的阶越低，评估越精确，越有价值。

例：设 $f(n)=n^2+n$ ，有
$f(n)=\Omicron(n^2)$ ，取 $c=2,n_0=1$ 即可
$f(n)=\Omicron(n^3)$ ，取 $c=1,n_0=2$ 即可

常见的时间复杂度关系

O(1)<O(log(n))<O(n)<O(nlogn)<O(n^{2})

$O(2^{n})$ 和 $O (n!)$ 大于以上的所有时间复杂度，具体原因参考图像。

时间复杂度计算：递归方程

加、减、乘、除、比较、赋值等操作，一般被看作是基本操作，并约定所用的时间都是一个单位时间；通过计算这些操作分别执行了多少次来确定程序总的执行步数。一般来说，算法中关键操作的执行次数决定了算法的时间复杂度。
比较简单的算法时间复杂性估计通常需要观察在for、while循环中的关键操作执行次数，在这里我们只讨论一种比较复杂的时间复杂度计算问题：求递归方程解的渐近阶的方法。递归式就是一个等式，代表了递归算法运算时间和n的关系，通过更小输入的函数值来描述一个函数。那么如何求得递归算法的Θ渐进界呢？主要有三种方法。