算法之复杂度

2022-10-25 阅读量

算法中基本操作重复执行的次数是问题规模$n$的某个函数，用$T(n)$表示，$n$称为问题的规模。

在复杂度的度量上，我们使用相对增长率来分析算法，使用渐进记号来表述算法复杂度。

通俗来说：

常数函数：设 $T(n) = 9$。存在 $n_0 = 0, c = 9, T(n) \leq c \cdot 1$，即可得到 $T(n) = O(1)$。实际上大$O$是包含所有增长率超过规模函数的函数集合，如 $T(n) = O(n)$ 也成立，所以大$O$也称作渐进上界。
线性函数：设 $T(n) = 3n + 2$。存在 $n \geq 2 = n_0, c = 4, T(n) \leq c \cdot n$，即可得到 $T(n) = O(n)$
平方函数：设 $T(n) = 10n^2 + 4n + 2$。存在$n \geq 5 = n_0, c = 11, T(n) \leq c \cdot n^2$，即可得到 $T(n) = O(n^2)$

$n \geq 2, 10n^2 + 4n + 2 \leq 10n^2 + 5n$

$n \geq 5, 10n^2+5n \leq 11n^2$

使用大$O$表示法，对于多项式，只保留最高次幂的项
指数函数：设 $T(n) = 6 \times 2^n + n^2$。存在 $n \geq 4 = n_0, c = 7, T(n) \leq c \cdot 2^n$，即可得到 $f(n) = O(2^n)$
加法规则：设 $T_1(m) = O(f(m)), T_2(n) = O(g(n))$，则2段程序连着使用时，$T_1(m) + T_2(n) = O(max\{f(m),g(n)\})$
乘法规则：设 $T_1(m) = O(f(m)), T_2(n) = O(g(n))$，则2段程序嵌套使用时，$T_1(T_2(n)) + = O(f(m) \times g(n))$

设 $T(n) = 10 n^2 + 4 n + 2$。存在 $n \geq 1, c = 10, T(n) \geq c n^2$，即可得到 $T(n) = \Omega(n^2)$。同大$O$一样，$\Omega$ 包含了所有增长率低于规模函数的函数，所以 $\Omega$ 也称作渐进下界或者最小运行时。

对于 $T(n) = 10n^2 + 4n + 2$，$T(n) = O(n^2) = \Omega(n^2)$，可得 $T(n) = \Theta(n^2)$。$\Theta$ 也称作准确界。

我们能够通过计算极限 $\lim\limits_{n \to \infty} {\dfrac {T(n)} {f(n)}}$ 来确定2个函数的相对增长率，必要的时候可以使用洛必达法则。

$\color{green} O(1) < O(log_2 n) < O(\sqrt n) < O(n) < O(n log_2 n) \color{blue} < O(n^2) < O(n^3) \color{red} < O(2^n) < O(3^n) < O(n!)$