算法设计与分析初步

算法分析基础

算法分析基本概念

算法分析（analysis of algorithms） 是对一个算法需要多少计算时间和存储空间作定量得分析，确定算法在什么样得环境下能够有效地运行。分析其在最好、最坏和平均情况下的执行情况，并对同一问题不同算法的有效性作出比较。

全面分析算法的两个阶段：

事前分析（a priori analysis）：

确定每条语句的执行次数；
求出该算法的一个时间限界函数（关于问题规模 n 的函数）。

事后测试（a posterior testing）：

作时空性能分布图。

算法的执行时间：

同一条语句在一个算法中的执行次数称为频率计数（frequency count），由算法直接确定，与所用的机器无关，且独立于程序设计语言。
语句的时间总量 = 频率计数 × 执行一次该语句所需要的时间
算法的执行时间就是构成算法的所有语句的执行时间总量之和。

时间复杂度的形式化定义：

算法的时间复杂度用 $T(n)$ 表示，空间复杂度用 $S(n)$ 表示，其中 $n$ 是问题的规模。

最坏情况下：

$T_{max}(n) = \max\{ T(I) \mid \mathrm{size}(I) = n \}$

最好情况下：

$T_{min}(n) = \min\{ T(I) \mid \mathrm{size}(I) = n \}$

平均情况下：

$T_{avg}(n) = \sum_{\mathrm{size}(I) = n} p(I) T(I)$

其中 $I$ 是问题的规模为 $n$ 的实例， $p(I)$ 是实例 $I$ 出现的概率。

计算时间的渐进表示

定义： 如果存在两个正常数 $c$ 和 $n_0$ ，对于所有的 $n \geq n_0$ ，有 $|f(n)| \leq c|g(n)|$ ，则记作 $f(n) = O(g(n))$ .

当 $n$ 充分大时， $f(n)$ 有上界，一个常数倍的 $g(n)$ 是 $f(n)$ 的一个上界， $f(n)$ 的阶不高于 $g(n)$ 的阶。

$O$ 的性质： 对于非负的 $f(n)$ 和 $g(n)$ ，有如下性质：

$f(n) = O(f(n))$ ；
$O(f(n)) + O(g(n)) = O(f(n) + g(n))$ ；
$O(f(n)) O(g(n)) = O(f(n) g(n))$ ；
$O(f(n)) + O(g(n)) = O(\max\{ f(n), g(n) \})$ ；
$O(cf(n)) = O(f(n))$ ，其中 $c$ 是一个正的常数；
如果 $g(n) = O(f(n))$ ，则 $O(f(n)) + O(g(n)) = O(f(n))$ .

证明 $O(f(n)) + O(g(n)) = O(\max\{ f(n), g(n) \})$ .

证：不妨设 $p(n) = \max\{ f(n), g(n) \}$ ，
设 $f'(n) = O(f(n))$ ，则存在 $c_1, n_1$ ，当 $n \geq n_1$ 时， $f'(n) \leq c_1 f(n)$ ；
设 $g'(n) = O(g(n))$ ，则存在 $c_2, n_2$ ，当 $n \geq n_2$ 时， $g'(n) \leq c_1 g(n)$ ，
则 $O(f(n)) + O(g(n)) = f'(n) = g'(n)$ .

当 $n \geq \max\{ n_1, n_2 \}$ 时，

$f'(n) + g'(n) \leq c_1 f(n) + c_2 g(n) \leq c_1 p(n) + c_2 p(n) = (c_1 + c_2) p(n)$

即存在 $c_3 = c_1 + c_2$ ， $n_3 = \max\{ n_1, n_2 \}$ ，当 $n \geq n_3$ 时， $f'(n) + g'(n) \leq c_3 p(n)$ .
故 $O(f(n)) + O(g(n)) = O(\max\{ f(n), g(n) \})$ .

数量级对算法有效性的影响： 从计算时间上，算法可以分为两类：

多项式时间算法：用多项式来计算时间限界的算法，例如

$O(1) < O(\log{n}) < O(n) < O(n \log{n}) < O(n^2) < O(n^3)$

指数时间算法：用指数函数来计算时间限界的算法，例如

$O(2^n) < O(n!) < O(n^n)$

定义： 如果存在两个正常数 $c$ 和 $n_0$ ，对于所有的 $n \geq n_0$ ，有 $|f(n)| \geq c|g(n)|$ ，则记作 $f(n) = \Omega(g(n))$ .

当 $n$ 充分大时， $f(n)$ 有下界，一个常数倍的 $g(n)$ 是 $f(n)$ 的一个下界， $f(n)$ 的阶不低于 $g(n)$ 的阶。

$\Omega$ 的性质： 对于非负的 $f(n)$ 和 $g(n)$ ，有如下性质：

$f(n) = \Omega(f(n))$ ；
$\Omega(f(n)) + \Omega(g(n)) = \Omega(f(n) + g(n))$ ；
$\Omega(f(n)) \Omega(g(n)) = \Omega(f(n) g(n))$ ；
$\Omega(f(n)) + \Omega(g(n)) = \Omega(\min\{ f(n), g(n) \})$ ；
$\Omega(cf(n)) = \Omega(f(n))$ ，其中 $c$ 是一个正的常数；
如果 $g(n) = \Omega(f(n))$ ，则 $\Omega(f(n)) + \Omega(g(n)) = \Omega(f(n))$ .

定义： 如果存在正常数 $c_1, c_2$ 和 $n_0$ ，对于所有的 $n \geq n_0$ ，有 $c_1|g(n)| \leq |f(n)| \leq c_2|g(n)|$ ，则记作 $f(n) = \Theta(g(n))$ .

一个算法若满足 $f(n) = \Theta(g(n))$ ，则意味着该算法在最好和最坏情况下的计算时间就一个常数因子范围内是相同的。

$\Theta$ 的性质： 对于非负的 $f(n)$ 和 $g(n)$ ，有如下性质：

$f(n) = \Theta(f(n))$ ；
$\Theta(f(n)) + \Theta(g(n)) = \Theta(f(n) + g(n))$ ；
$\Theta(f(n)) \Theta(g(n)) = \Theta(f(n) g(n))$ ；
$\Theta(f(n)) + \Theta(g(n)) = \Theta(\max\{ f(n), g(n) \})$ ；
$\Theta(cf(n)) = \Theta(f(n))$ ，其中 $c$ 是一个正的常数。
如果 $g(n) = \Theta(f(n))$ ，则 $\Theta(f(n)) + \Theta(g(n)) = \Theta(f(n))$ .

渐近表示函数具有传递性：

$f(n) = O(g(n)), g(n) = O(h(n)) \Rightarrow f(n) = O(h(n))\\ f(n) = \Omega(g(n)), g(n) = \Omega(h(n)) \Rightarrow f(n) = \Omega(h(n))\\ f(n) = \Theta(g(n)), g(n) = \Theta(h(n)) \Rightarrow f(n) = \Theta(h(n))\\$

常用的整数求和公式：

$\begin{aligned} \sum_{1 \leq i \leq n} 1 &= \Theta(n)\\ \sum_{1 \leq i \leq n} i &= \frac{n(n + 1)}{2} = \Theta(n^2)\\ \sum_{1 \leq i \leq n} i^2 &= \frac{n(n + 1)(2n + 1)}{6} = \Theta(n^3) \end{aligned}$