复杂度

  • 什么是算法
    • 算法的简要定义
    • 算法的基本特征
    • 算法与程序的区别
  • 复杂度分析
    • 如何确定输入规模
    • 什么是时间复杂度,什么是空间复杂度
    • 什么是最坏情形复杂度?最好情形复杂度?平均情形复杂度?
    • 复杂度的渐进阶及其数学运算
      • 例:算法分析题1 (p7)
    • 简单问题的算法设计
      • 例:算法实现题1 (P7-10)

算法与程序

算法(algorithm)是由若干条指令组成的有穷序列,满足:

  1. 输入(Input):有0~n个外部量作为输入(可以没输入);
  2. 输出(Output):产生至少一个量输出;
  3. 确定性(Deterministic):组成算法的每条指令清晰,无歧义;
  4. 可行性(Feasibility):由元指令组成;
  5. 有限性(Halt):每条指令执行的次数和时间都是有限的;

程序(program)与算法不同,程序是算法用程序设计语言的具体描述,并且程序可以不满足有限性(e.g. 操作系统)

算法复杂性分析

算法复杂性体现在所需的计算机资源多少上,包括时间资源与空间资源(存储器),所以算法复杂性分为:时间复杂性空间复杂性

我们一般用一个函数表示复杂性。设 $N$,$I$,$A$ 分别表示问题规模、输入、算法,则复杂性 $C=F(N,I,A)$,有时候省略 $A$。可以将时间复杂性表示为 $T=T(N,I)$,空间复杂性为 $S=S(N,I)$.

时间复杂度

设元指令有 $k$ 种,分别需要 $t_1, t_2, \cdot, t_k$ 时间,在某种算法中分别用了 $e_1, e_2, \cdot, e_k$ 次,并且 $e_i=e_i(N,I)$。所以:

考虑到 $I$ 有多种,不妨只考虑某些特殊情况,所以我们只考虑最坏情况,最好情况和平均情况:

其中,$D_N$ 是合法输入集,$P(I)$ 是概率。

一般来讲,如果问题规模$N\rightarrow\infty$,则 $T(N)\rightarrow \infty$,我们定义渐进复杂度 $\widetilde{T}(N)$,满足 $\lim_{N\rightarrow\infty}\frac{T(N)-\widetilde{T}(N)}{T(N)}=0$,从而 $T(N)$ 在问题规模增大时可用 $\widetilde{T}(N)$ 代替,从而可以简化 $T(N)$。


那么我们要如何选择 $\widetilde{T}(N)$ 呢?这里我们模仿高数中的高阶无穷大,定义如下概念。

我们设 $f(x)$ 和 $g(x)$ 是两个正函数,并且在无穷远处趋于正无穷:

  1. $\exists C\in \mathbb{R^+}, N_0\in\mathbb{N}$,使得当 $N\geq N_0$时,有 $f(N)\leq Cg(N)$,则 $f(x)$ 的阶不高于 $g(x)$,记为 $f(x)=O(g(N))$;
  2. $\exists C\in \mathbb{R^+}, N_0\in\mathbb{N}$,使得当 $N\geq N_0$时,有 $f(N)\geq Cg(N)$,则 $f(x)$ 的阶不低于 $g(x)$,记为 $f(x)=\Omega(g(N))$;
  3. 若 $f(N)=O(g(N))$ 且 $f(N)=\Omega(g(N))$,则 $f(N)$ 与 $g(N)$ 同阶记为 $f(x)=\theta(g(x))$

上面的定义有点绕,实际上我们可以简化为:

这么一来,我们就可以“上界阶”描述渐进复杂度 $\widetilde{T}(N)$,同时用“下界阶”来描述某类问题的最优算法。

于是我们可以将同一类渐进复杂度统一用一种函数表示。常用的有:

注:$\log n$ 在算法中常按 $\log_2 n$ 来计算,但实际上取任何底数都行,因为我们可以证明不同底数都是同阶的。

时间复杂度的相关计算

时间复杂度的运算规则:

  1. $O(f)+O(g)=O(\max(f,g))$
  2. $O(f)+O(g)=O(f+g)$
  3. $O(f)O(g)=O(fg)$
  4. $O(Cf)=O(f)$
  5. $f=O(f)$

下面是几个常用的结论:

$$ \text{Let}\;f(n)=a_kn^k+a_{k-1}n^{k-1}+\cdot+a_1n+a_0\\ \text{Then}\;f(n)=O(n^k)=\Omega(n^k)=\theta(n^k) $$

Stirling's Formula:证明1 证明2 $$ n!\approx\sqrt{2n\pi}\left(\frac{n}{e}\right)^n\\ \text{Or}\;n!\approx\sqrt{\frac{2\pi}{n+1}}\left(\frac{n+1}{e}\right)^{n+1} $$ 利用 Stirling 公式我们可以证得: $$ \log n! =\theta(n\log n) $$


例题:求下列函数的渐进表达式:
$$ 3n^2+10n \quad n^2/10+2^n\\ 21+1/n \quad \log n^3 \quad 10\log 3^n $$

解:
$$ O(3n^2+10n)=O(3n^2)+O(10n)=O(3n^2)=O(n^2)\\ O(n^2/10+2^n)=O(n^2/10)+O(2^n)=O(2^n)\\ O(21+1/n)=O(21)+O(1/n)=O(21)=O(1)\\ O(\log n^3)=O(3\log n)=O(\log n)\\ O(10\log 3^n)=O(10 n \log 3)=O(n) $$

空间复杂度

空间复杂度 = 算法所用空间 - 输入数据所用空间,记为 $S(n)$

算法研究の过程

  1. 设计 Algorithm Design
  2. 伪代码描述 Pseudo Code
  3. 正确性 Proof of Correctness
  4. 复杂度分析 Algorithm Analysis
    • 时间复杂度 Time Complexity
    • 空间复杂度 Space Complexity
  5. 实现 Algorithm Implementation