算法设计与分析Ch02

弃坑了，转战Jeff的《Algorithms》

第二章 算法分析的数学基础

序列求和的方法

数列求和公式：等差、等比数列与调和级数

$$\sum_{k=1}^{n} a_k = \frac{n(a_1+a_n)}{2},\qquad\sum_{k=0}^{n} aq^k = \frac{a(1-q^{n+1})}{1-q}$$

$$\sum_{k=0}^{\infty} aq^k = \frac{a}{1-q} (q<1),\qquad \sum_{k=1}^{n} \frac{1}{k} = \ln n + O(1)$$

估计和式上界的放大法（下界同理）

1. $\sum_{k=1}^{n} a_k \leq na_{max}$

2. 假设存在常数 $r<1$, 使得对一切 $k \geq 0$ 有 $\frac{a_{k+1}}{a_k} \leq r$ 成立

   $\sum_{k=0}^{n} a_k \leq \sum_{k=0}^{\infty} a_0r^k = a_0 \sum_{k=0}^{\infty} r^k = \frac{a_0}{1-r}$

3. 积分法估计上界

递推方程与算法分析

递推方程

设序列 $a_0, a_1, \cdots, a_n, \cdots$ 简记为 $\{a_n\}$，一个把 a 与其些个 $a_i(i<n)$ 联系起来的等式叫做关于序列 $\{a_n\}$ 的递推方程

递推方程的求解:

给定关于序列 $\{a_n\}$ 的递推方程和若干初值，计算 $a_n$

例子：Fibonacci 数列

Hanoi塔问题

插入排序

小结

• 递推方程的定义及初值
• 递推方程与算法时间复杂度的关系
• Hanoi 塔的递归算法
• 插入排序的递推算法

递推方程的解法

迭代法

• 不断用递推方程的右部替换左部
• 每次替换，随着 $n$ 的降低在和式中多出一项
• 直到出现初值停止迭代
• 将初值代入并对和式求和
• 可用数学归纳法验证解的正确性

换元迭代

• 将 $n$ 的递推式换成对其他变元 $k$ 的递推式
• 对 $k$ 直接代入递推式
• 将解（关于 $k$ 的函数）转换成关于 $n$ 的函数

假设 $n=2^k$，递推方程如下:

$$W(n) = 2 W(n/2) + n - 1 \\ W(1) = 0$$

换元:

$$W(2^k) = 2 W(2^{k-1}) + 2^k - 1 \\ W(0) = 0$$

小结

迭代法解递推方程

• 直接迭代，代入初值，然后求和
• 对递推方程和初值进行还原，然后求和，求和后再换元回去，得到原始递推方程的解
• 用数学归纳法验证解的正确性

差消法

如果递推关系比较复杂的时候，直接迭代会非常的困难。 我们要尽量的化简，把高阶的递推方程化简成一阶的 这样才能继续迭代。

快速排序

• 假设 $A[p \cdots r]$ 的元素彼此不等
• 以首元素 $A[1]$ 对数组 $A[p \cdots r]$ 划分，得到:
  • 小于 $x$ 的元素放在 $A[p \cdots q-1]$
  • 大于 $x$ 的元素放在 $A[q+1 \cdots r]$
• 递归对 $A[p \cdots q-1]$ 和 $A[q+1 \cdots r]$ 排序

工作量 = 子问题的工作量 + 划分所用工作量

输入情况

• 有 n 种可能的输入

x 排好序位置	子问题 1 规模	子问题 2 规模
1	0	n-1
2	1	n-2
3	2	n-3
$\cdots$	$\cdots$	$\cdots$
n-1	n-2	1
n	n-1	0

• 对于每个输入, 比较次数都是 n-1

工作量总和

$$T(0) + T(n-1) + n-1 \\ T(1) + T(n-2) + n-1 \\ T(2) + T(n-3) + n-1 \\ \cdots \\ + T(n-1) + T(0) + n-1 \\ = 2[T(1)+...+T(n-1)] + n(n-1)$$

快速排序平均工作量

假设首元素排好序在每个位置是等概率的
递推式为:

$$T(n) = \frac{2}{n} \sum_{i=1}^{n-1} T(i) + O(n), n \geqslant 2 \\ T(1) = 0$$

对于高阶方程应该先化简, 然后迭代

差消化简

利用两个方程相减, 将右边的项尽量消去, 将左边的项尽可能简化

$$T(n) = \frac{2}{n} \sum_{i=1}^{n-1} T(i) + cn \\ nT(n) = 2 \sum_{i=1}^{n-1} T(i) + cn^2 \\$$

得到

$$(n-1)T(n-1) = 2 \sum_{i=1}^{n-2} T(i) + c(n-1)^2$$

将上述两式相减:

$$\begin{align*} nT(n) - (n-1)T(n-1) & = 2T(n-1) + cn^2 - c(n-1)^2 \\ & = 2T(n-1) + 2cn - c \\ & = 2T(n-1) + 2c(n-1) \\ & = 2 T(n-1) + c_1n \end{align*}$$

得到：

$$\frac{T(n)}{n+1} = \frac{T(n-1)}{n} + \frac{c_1}{n+1}$$

迭代求解:

$$\begin{align*} \frac{T(n)}{n+1} & = \frac{T(n-1)}{n} + \frac{c_1}{n+1} \\ & = c_1 [\frac{1}{n+1} + \frac{1}{n} + \cdots + \frac{1}{3}] + \frac{T(1)}{2} \\ & = c_1 [\frac{1}{n+1} + \frac{1}{n} + \cdots + \frac{1}{3}] \\ & = \Theta(\log n) \end{align*}$$

因此最终可以得到:

$$T(n) = \Theta(\log n)$$

递归树

递归树的概念

• 递归树是迭代计算的模型.
• 递归树的生成过程与迭代过程一致.
• 递归树上所有项恰好是迭代之后产生和式的项.
• 对递归树上的项求和就是迭代后方程的解.

二分归并排序

递归树的生成规则

• 初始, 递归树只有根结点, 其值为 $W(n)$
• 不断继续迭代过程：
  • 将函数项叶结点的迭代式 $W(m)$ 表示成二层子树
  • 用该子树替换该叶结点
• 继续递归树的生成，直到树中无函数项(只有初值)为止.

求和
方程: $T(n) = T(n/3) + T(2n/3) + n$，递归树层数 $k$，每层 $O(n)$

$$： \begin{align*} & n (\frac{2}{3})^k = 1 \\ & \Rightarrow (\frac{2}{3})^k = n \\ & \Rightarrow k = O(\log _{\frac{3}{2}} n) \\ & \Rightarrow T(n) = Θ(n log n) \end{align*}$$

小结

• 递归树是迭代的图形表述
• 递归树的生成规则
• 如何利用递归树求解递推方程

主定理

应用背景

求解递推方程:
$T(n) = a T(\frac{n}{b}) + f(n)$

其中:

1. $a$: 递归后的子问题个数
2. $n/b$: 递归后子问题的规模
3. $f(n)$: 递归过程及组合子问题的解的工作量

二分检索: $T(n) = T(n/2)+1$

二分归并排序: $T(n) = 2T(n/2)+n-1$

主定理的内容与证明

定理: 设$a≥1, b>1$为常数, $f(n)$为函数, $T(n)$ 为非负整数，定义为：$T(n) = aT(n/b) + f(n)$，则:

1. 若 $f(n) = \Theta(n^{\log_b a - \epsilon}), \epsilon > 0$，则 $T(n) = \Theta(n^{\log_b a})$
2. 若 $f(n) = \Theta(n^{\log_b a}), \epsilon > 0$，则 $T(n) = \Theta(n^{\log_b a}\log n)$
3. 若 $f(n) = \Omega(n^{\log_b a + \epsilon}), \epsilon > 0$，且对于某个常数 $c < 1$ 和 $n$ 足够大的 $n$ 有 $af(n/b) ≤ cf(n)$，则 $T(n) = \Theta(f(n))$

证明：
对于 $T(n) = aT(n/b) + f(n)$，设 $n = b^k$，则有：

$$\begin{align*} T(n) & = aT(n/b) + f(n) \\ &= a[aT(n/b^2) + f(n/b)] + f(n) \\ & = a^2T(n/b^2) + af(n/b) + f(n) \\ &= a^3T(n/b^3) + a^2f(n/b^2) + af(n/b) + f(n) \\ &= \cdots \\ &= a^k T(1) + \sum_{i=0}^{k-1} a^i f(\frac{n}{b^i}) \\ &= c_1 n^{\log_b a} + \sum_{i=0}^{k-1} a^i f(\frac{n}{b^i}), \quad T(1) = c_1 \end{align*}$$

其中：

• 第一项为所有最小子问题的计算工作量
• 第二项为迭代过程归约到子问题及综合解的工作量

情形一： $f(n) = \Theta(n^{\log_b a - \epsilon}), \epsilon > 0$

$$\begin{align*} T(n) &= c_1 n^{\log_b a} + \sum_{j=0}^{k-1} a^j f(\frac{n}{b^j}) \\ &= c_1 n^{\log_b a} + O(\sum_{j=0}^{\log_b n -1} a^j (\frac{n}{b^j})^{\log_b a - \epsilon}) \\ &= c_1 n^{\log_b a} + O(n^{\log_b a - \epsilon} \sum_{j=0}^{\log_b n -1} \frac{a^j}{(b^{\log_b a - \epsilon})^j}) \\ &(使用： \frac{1}{(b^{\log_b a - \epsilon})^j} = \frac{b^{\epsilon j}}{(b^{\log_b a})^j} = \frac{b^{\epsilon j}}{a^j}) \\ &= c_1 n^{\log_b a} + O(n^{\log_b a - \epsilon} \sum_{j=0}^{\log_b n -1} (b^\epsilon)^j) \\ &= c_1 n^{\log_b a} + O(n^{\log_b a - \epsilon} \frac{b^{\epsilon \log_b n} - 1}{b^\epsilon - 1})\\ &= c_1 n^{\log_b a} + O(n^{\log_b a - \epsilon} n^\epsilon) \\ &= \Theta(n^{\log_b a}) \end{align*}$$

情形二： $f(n) = \Theta(n^{\log_b a}), \epsilon > 0$

$$\begin{align*} T(n) &= c_1 n^{\log_b a} + \sum_{j=0}^{k-1} a^j f(\frac{n}{b^j}) \\ &= c_1 n^{\log_b a} + \Theta(\sum_{j=0}^{\log_b n -1} a^j (\frac{n}{b^j})^{\log_b a}) \\ &= c_1 n^{\log_b a} + \Theta(n^{\log_b a} \sum_{j=0}^{\log_b n -1}\frac{a^j}{a^j}) \\ &= c_1 n^{\log_b a} + \Theta(n^{\log_b a} \log n) \\ &= \Theta(n^{\log_b a} \log n) \end{align*}$$

情形三： $f(n) = \Omega(n^{\log_b a + \epsilon}), \epsilon > 0,\quad af(n/b) ≤ cf(n)$

$$\begin{align*} T(n) &= c_1 n^{\log_b a} + \sum_{j=0}^{k-1} a^j f(\frac{n}{b^j}) \\ & \leqslant c_1 n^{\log_b a} + \sum_{j=0}^{k-1} c^j f(n) \\ & = c_1 n^{\log_b a} + f(n) \frac{c^{\log_b n} - 1}{c - 1} \\ &= c_1 n^{\log_b a} + \Theta(f(n)) \\ & = \Theta(f(n)) \end{align*}$$

Q.E.D.

主定理的应用

例题1： 求解递推方程 $T(n) = 9T(n/3) + n$.

解： 上述方程 $a = 9, b = 3, f(n) = n, \epsilon = 1$，根据主定理，有：$n^{\log_3 9} = O(n^{\log_3 9}) = n^2$，因此 $f(n) = O(n^{\log_3 9 - 1})$。

由主定理，$T(n) = \Theta(n^2)$

例题2： 求解递推方程 $T(n) = T(2n/3) + 1$.

解： 上述方程 $a = 1, b = \frac{3}{2}, f(n) = 1, \epsilon = 1$，根据主定理，有：$f(n) = \Theta(n^{\log_{\frac{3}{2}} 1}) = \Theta(1)$。

由主定理，$T(n) = \Theta(1 \cdot \log n) = \Theta(\log n)$

例题3： 求解递推方程 $T(n) = 3T(n/4) + n \log n$.

解： 上述方程 $a = 3, b = 4, f(n) = n \log n$，根据主定理，有：$f(n) = n \log n = \Omega(n^{\log_4 3 + \epsilon}) \approx \Omega(n^{0.793 + \epsilon})$，取 $\epsilon = 0.2$ 即可。

要使 $a f (n/b) \leq c f (n)$ 成立，代入 $f (n) = n \log n$，得到：

$$3 (n/4) \log (n/4) \leq c n \log n$$

只要 $c > 3/4$, 上述不等式可以对所有充分大的 $n$ 成立.

由主定理，有 $T(n)=\Theta(f(n))=\Theta(n\log n)$

不能使用主定理的情况

小结

• 使用主定理求解递推方程需要满足什么条件?
• 主定理怎样用于算法复杂度分析?