算法与程序

算法（algorithm）是由若干条指令组成的有穷序列，满足：

输入（Input）：有0~n个外部量作为输入（可以没输入）；
输出（Output）：产生至少一个量输出；
确定性（Deterministic）：组成算法的每条指令清晰，无歧义；
可行性（Feasibility）：由元指令组成；
有限性（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)$。所以：

\[T(N,I)=\sum_{i=1}^k t_i e_i(N,I)\]

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

\[T_\max(N)=\max_{I\in D_N}\sum_{i=1}^kt_ie_i(N,I)=T(N,I^*)\\ T_\min(N)=\min_{I\in D_N}\sum_{i=1}^kt_ie_i(N,I)=T(N,\widetilde{I})\\ T_\text{avg}(N)=\sum_{I\in D_N}P(I)T(N,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)$ 是两个正函数，并且在无穷远处趋于正无穷：

$\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))$；
$\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))$；
若 $f(N)=O(g(N))$ 且 $f(N)=\Omega(g(N))$，则 $f(N)$ 与 $g(N)$ 同阶记为 $f(x)=\theta(g(x))$

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

\[\lim_{N\rightarrow\infty} \frac{g(x)}{f(x)}= \begin{cases} C\sim\infty\Rightarrow f不高于g\\ \;\\ C\Rightarrow f,g同阶\\ \;\\ 0\sim C\Rightarrow f不低于g \end{cases}\]

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

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

\[O(1)<O(\log\log n)<O(\log n)<O(n)<O(n\log n)<O(n^2)<\cdots\\ <O(n^k)<O(k^n)<O(n!)<O(n^n)\]

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

时间复杂度的相关计算

时间复杂度的运算规则：

$O(f)+O(g)=O(\max(f,g))$
$O(f)+O(g)=O(f+g)$
$O(f)O(g)=O(fg)$
$O(Cf)=O(f)$
$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)$

算法研究の过程

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

上篇简介

下篇递归与分支