算法设计与分析Ch01

弃坑了，转战Jeff的《Algorithms》

第一章：算法基础

第一节：算法设计的两个例子

例1：调度问题

假设有n个任务，每个任务都有一个长度，希望按照长度的顺序进行调度，使得所有任务完成时间之和最短。

标号	1	2	3	4	5
加工时间$t_i$	3	8	5	10	15

贪心算法

贪心算法的基本思想是：每次选择最短的任务进行分配，直到所有任务都分配完毕。

1. 选择最短的任务进行分配。
2. 重复步骤1，直到所有任务都分配完毕。

按照贪心算法，将任务按照耗时从小到大进行排序即可。

任务集：$S$ = {1, 2, 3, 4, 5}
加工时间：$t_j \in \mathbb{Z}^+$，$j = 1, 2, 3, 4, 5$
任务调度方案为：$I$ = {$i_1, i_2, i_3, i_4, i_5$}
完成时间为，$t(I) = \sum_{k = 1}^5 (5-k+1) t_{i_k}$
目标是求$I^* = \arg\min_{I} t(I)$，即完成时间最短的任务调度方案。
(调整法即可证明上述贪心算法所得解的最优性)

能否对所有情况最优？

反例：背包问题

假设有n件物品，每件物品都有一个重量和价值，希望选择若干件物品，使得总重量不超过背包容量，且总价值最大。

贪心算法的基本思想是：每次选择单位重量价值最高的物品进行分配，直到背包容量不足。

标号	1	2	3	4
重量$w_i$	3	4	5	2
价值$v_i$	7	9	9	2

背包容量为6。

贪心算法的步骤如下：

1. 选择价值最高的物品进行分配。
2. 重复步骤1，直到背包容量不足。

按照贪心算法：$\frac{7}{3} > \frac{9}{4} > \frac{9}{5} > \frac{2}{2}$
所以选择物品1，再加上物品4，重量为5，价值为9；但是，选择物品2、4，重量为6，价值为11，优于贪心法的解。

因此贪心法不一定为最优

算法设计

1. 问题建模
2. 选择什么算法？如何描述算法？
3. 是否能得到最优解？如何证明？
4. 如果不是，能否找到反例？

例2：投资问题

假设 $m$ 元钱，投资 $n$ 个项目，效益函数为 $f_i(x)$，表示第 $i$ 个项目投资 $x$ 元的效益。求如何分配资金，使得总收益率最大。

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	0	0
1	11	0	2	20
2	12	5	10	21
3	13	10	30	22
4	14	15	32	23
5	15	20	40	24

输入：$n, m, f_i(x), i=1,2,\cdots,n, x=1,2,\cdots,m$
求解：$n$维向量$x = [x_1, x_2, \cdots, x_n]$，$x_i$ 表示第 $i$ 个项目投资的金额。
目标函数：

• $\max \sum_{i=1}^n f_i(x_i)$

约束条件：

• $\sum_{i=1}^n x_i = m$

暴力算法

暴力法的基本思想是：枚举所有可能的分配方案，计算每种方案的收益率，选择收益率最高的方案。

对所有满足$\sum_{i=1}^n x_i = m$的向量$x$，计算$\sum_{i=1}^n f_i(x_i)$，选择收益率最高的方案。

方程：$x_1 + x_2 + \cdots + x_n = m$的非负整数解的个数估计：
将可行解表示为0-1序列：$m$个1，$n-1$个0：

例如，对于$n=4, m=7$，可行解 $[1,2,3,1] \Leftrightarrow$ 序列：1011011101

序列的个数为：$C_{m+n-1}^m = \frac{(m+n-1)!}{m!n!} \simeq (1+\epsilon)^{m+n-1}$

有无更好的算法？

小结

• 建模：对输入参数和解给出形式化或半形式化的描述
• 设计算法：采用什么算法？如何证明算法的正确性？
• 分析：效率如何？是否存在更好的算法？

第二节：计算复杂度-排序问题

例3：排序算法的效率

算法	最坏情况下	平均情况下
插入排序	O(n²)	O(n²)
冒泡排序	O(n²)	O(n²)
快速排序	O(n²)	O(nlogn)
堆排序	O(nlogn)	O(nlogn)
二分归并排序	O(nlogn)	O(nlogn)

默认是从小到大排序。

插入排序

• 排序过程: 对于每个元素，它与它前面的元素依次比较，并将它插入到合适的位置。（向前比对，往前插）

  

冒泡排序

• 排序过程: 对于每个元素，它与它后面的元素依次比较，并将它交换到合适的位置。（向后比对，往后冒）

  

快速排序

• 排序过程: 选取一个元素作为基准，将所有小于基准的元素放到左边，所有大于基准的元素放到右边，然后递归地排序左右两边。

  

二分归并排序

• 二分归并排序的过程: 先将数组分成两半，分别排序，然后将两个有序数组合并成一个有序数组。

  

小结

第三节: 货郎问题与计算复杂性

例4：货郎问题

有 $n$ 个城市，已知任两个城市之间的距离。求一条恰经过每个城市1次的回路，使得回路的总长度最短。

• 建模与算法

输入: 有穷个城市的集合 $C = {c_1, c_2, \cdots, c_n}$, 其中 $d(ci,cj) = d(cj,ci) \in \mathbb{Z}^+, 1 \leqslant i < j \leqslant n$

解: $1, 2, \cdots, n$ 的排列 $k_1, k_2, \cdots, k_n$ 使得:
$\min\{d(c_{k_n},c_{k_1}) + \sum_{i=1}^{n-1} d(c_{k_i},c_{k_{i+1}}) \}$

例5: 0-1背包问题

有 $n$ 件物品，第 $i$ 件物品的重量为 $w_i$，价值为 $v_i$。背包最多允许装入的重量为 $B$。问如何选择装入背包的物品，使得总价值最大。

e.g.：$n = 4, B = 6$，物品重量与价值如下：

标号	1	2	3	4
重量$w_i$	3	4	5	2
价值$v_i$	7	9	9	2

0-1背包问题建模

问题的解:
0-1向量 $[x_1, x_2, \cdots, x_n]$
$ x_i = 1 \Leftrightarrow $ 物品 $i$ 装入背包
目标函数：

• $\max \sum_{i=1}^n v_i x_i$

约束条件：

• $\sum_{i=1}^n w_i x_i \leqslant B$
• $x_i = 0,1, i = 1, 2, \cdots, n$

例6: 双机调度问题

有 $n$ 项任务, 任务 $i$ 的加工时间为 $t_i, t_i \in \mathbb{Z}^+, i = 1, 2,\cdots,n$。用两台相同的机器加工，从 0 时刻开始计时，完成时间是后停止加工机器的时间。问如何把这些任务分配到两台机器上，使得完成时间达到最小？

e.g. 任务集 $ S = {1, 2, 3, 4, 5, 6}$

标号	1	2	3	4	5	6
加工时间$t_i$	3	10	6	2	1	7

机器1：1、2、4；机器2：3、5、6
此时完成时间为: $\max\{3+10+2, 6+1+7\} = 15$

双机调度问题建模

问题的解:
0-1向量 $[x_1, x_2, \cdots, x_n]$
$x_i = 1 \Leftrightarrow$ 任务 $i$ 被分配到机器1
$x_i = 0 \Leftrightarrow$ 任务 $i$ 被分配到机器2
不妨设机器1的加工时间 $\leqslant$ 机器2的加工时间，令 $T=t_1+t_2+\cdots+t_n$，$D = \left \lfloor \frac{T}{2} \right \rfloor$，机器1的加工时间不超过$D$，且达到最大。

NP-hard问题

• 这样的问题有数千个, 大量存在于各个应用领域。
• 至今没找到有效算法: 现有的算法的运行时间是输入规模的指数或更高阶函数。
• 至今没有人能够证明对于这类问题不存在多项式时间的算法。
• 从是否存在在多项式时间算法的角度看，这些问题彼此是等价的。这些问题的难度处于可有效计算的边界。

Algorithm + Data Structure = Programming

好的算法:

1. 提高求解问题的效率
2. 节省存储空间

算法的研究目标

1. 问题 → 建模并寻找算法 → 算法设计技术
2. 算法 → 算法的评价 → 算法分析方法
3. 算法类 → 问题复杂度估计 → 问题复杂度分析
4. 问题类 → 能够求解的边界 → 计算复杂性理论

算法研究的重要性

• 算法设计与分析技术在计算机科学与技术领域有着重要的应用背景。
• 算法设计分析与计算复杂性理论研究是计算机科学技术的核心研究领域。
• 1966-2005期间, Turing奖获奖50人, 其中10人以算法设计、7人以计算理论、自动机和复杂性研究领域的杰出贡献获奖。
• 计算复杂性理论的核心课题 “P=NP?” 是本世纪7个最重要的数学问题之一。

小结

• NP-hard问题的几个例子: 货郎问题、0-1背包问题、双机调度问题等
• NP-hard问题的计算现状
• 计算复杂性理论的核心——NP完全理论
• 算法研究的主要内容及重要意义

第四节：算法及其时间复杂度

基本概念

问题及实例

问题

• 需要回答的一般性提问, 通常含有干参数

问题描述

• 定义问题参数(集合、变量、函数等)
• 说明每个参数的取值范围及参数间的关系
• 定义问题的解
• 说明解满足的条件(优化目标或约束条件)

问题实例

• 参数的一组赋值可得到问题的一个实例

算法

算法

• 有限条指令的序列
• 这个指令序列确定了解决某个问题的一系列运算或操作

算法$A$解决问题$P$

• 把问题 $P$ 的任何实例作为算法 $A$ 的输入
• 每步计算都是确定性的
• $A$ 能够在有限步停机
• 输出该实例的正确的解

基本运算与输入规模

算法时间复杂度

• 针对指定基本运算, 计算算法所做运算次数

基本运算

• 比较, 加法, 乘法, 置指针, 交换等

输入规模

• 输入串编码长度：
  通常用下述参数度量: 数组元素个数、调度问题的任务个数、图的顶点数和边数等

算法基本运算次数可表为输入规模的函数
给定问题和基本运算就决定了一个算法类

输入规模例子

• 排序: 数组中元素个数 $n$
• 检索: 被检索数组的元素个数 $n$
• 整数乘法: 两个整数的位数 $m, n$
• 矩阵相乘: 行列的个数 $i, j, k$
• 图的遍历: 图的顶点数 $n$, 边数 $m$
• $\cdots$

基本运算例子

• 排序: 元素之间的比较
• 检索: 被检索数组元素 x 与数组元素的比较
• 整数乘法: 每位数字相乘(位乘) 1 次，$m$ 位和 $n$ 位整数相乘要做 $mn$ 次位乘
• 矩阵相乘: 每对元素素乘 1 次
  • $i \times j$ 矩阵与 $j \times k$ 矩阵相乘要做 $i \times j \times k$ 次乘法
• 图的遍历: 置指针
• $\cdots$

算法的两种时间复杂度

最坏情况时间复杂度(Worst-case time complexity)

• 算法求解输入规模为 $n$ 的实例所需要的最长时间，记为 $W(n)$

平均情况时间复杂度(Average-case time complexity)

• 在给定同样规模为 $n$ 的输入实例的概率分布下，算法求解这些实例的平均时间，记为 $A(n)$
• $A(n)$ 计算公式:
  $A(n) = \sum_{I \in S} P_I t_I$，其中 $S$ 是输入实例的集合，$P_I$ 是实例 $I$ 的概率，$t_I$ 是实例 $I$ 执行的基本运算次数

例7：检索问题

输入: 非降序排列的数组 $L$, 元素数量 $n$, 待检索元素 $x$
输出: $x$ 在数组 $L$ 中首次出现的下标 $j$, 若 $x$ 不在数组 $L$ 中, 输出 $0$
基本运算: 元素之间的比较

顺序检索算法

算法步骤:

1. 若 $x = L[j]$, 则输出 $j$。如果不等, 则不输出。
2. 如果不等, 则将 $j$ 加 1, 继续 $x$ 与 $L[j]$ 的比较。
3. 如果 $j > n$, 则说明 $x$ 不在 $L$ 中, 输出 $j = 0$。

实例:

1	2	3	4	5

• 若 $x = 4$, 需要比较 4 次
• 若 $x = 2.5$, 需要比较 5 次

设 $x$ 在 $L$ 中的概率是 $p$，且每个位置出现概率相同

• $w(n) = n$
• $A(n) = \sum_{i=1}^n i\frac{p}{n} + (1-p)n = \frac{p(n+1)}{2} + (1-p)n$
  当$p=\frac{1}{2}$时, $A(n) = \frac{n+1}{4} + \frac{n}{2} \approx \frac{3n}{4}$

二分查找算法

算法步骤:

1. 初始化 $j=1$, 将 $x$ 与 $L[j]$ 比较。
2. 如果 $x = L[j]$, 则输出 $j$ 并停止；如果 $x > L[j]$, 则将 $j$ 加 1，继续 $x$ 与 $L[j]$ 的比较；如果 $x < L[j]$, 则停机并输出 $j = 0$。
3. 如果 $j > n$, 停机并输出 $j = 0$。

实例:

1	2	3	4	5

• 若 $x = 4$, 需要比较 4 次
• 若 $x = 2.5$, 需要比较 3 次

算法分析:

• 基本运算为元素间的比较
• 比较次数为 $log n$, 即输入规模 $n$ 的对数

该二分查找算法的时间复杂度是 $O(log n)$, 与输入规模 $n$ 呈对数关系。相比顺序检索, 它的效率更高。

小结

• 算法的两种时间复杂度的定义
• 算法时间复杂度的计算方法

第五节：算法的伪代码表示

算法伪码描述

赋值语句: <-
分支语句: if ... then ... [else ...]
循环语句: while, for, repeat until
转向语句: goto
子程序: return
注释: //

这些是编程语言中常用的基本算法伪码描述元素。
通过组合使用这些元素, 可以描述各种算法的逻辑流程。
这种伪码描述方式便于理解和分析算法的工作原理。

算法伪码实例

例8: Euclid 算法 (m, n)

输入:非负整数 m, n, 其中 m 和 n 不全为 0
输出: m 和 n 的最大公约数
算法步骤:

1. while $m > 0$ do
2. $r \leftarrow n \mod m$
3. $n \leftarrow m$
4. $m \leftarrow r$
5. return $n$

运行实例:
输入：$n=36, m=15$：

while	n	m	r
第1次	36	15	6
第2次	15	6	3
第3次	6	3	0
	3	0	0

=> 输出 3

例9: 二分查找算法

输入: 从小到大排列得有序数组 $L[1,\cdots,n]$, 和待查找元素 $x$
输出: 若 $x$ 在 $L$ 中, 输出 $x$ 的下标 $j$; 否则输出 0
算法步骤:

1. $j \leftarrow 1$
2. while $j \leq n$ and $x > L[j]$ do $j \leftarrow j+1$
3. if $x = L[j]$ or $j > n$ then $j \leftarrow 0$
4. return $j$

例10: 插入排序算法

输入: $n$ 个数的数组 $A$
输出: 按照递增顺序排列的数组 $A$
算法步骤:

1. for $j \leftarrow 2$ to $n$ do
2. $\quad x \leftarrow A[j]$
3. $\quad i \leftarrow j-1 $ // 3-7 行把 $A[j]$ 插入 $A[1,\cdots,j-1]$ 中
4. while $i > 0$ and $x < A[i]$ do
5. $\quad A[i+1] \leftarrow A[i]$
6. $\quad i \leftarrow i-1$
7. $A[i+1] \leftarrow x$

例11: 二分归并排序

MergeSort(A, p, r)
输入: 数组 $A[p, \cdots, r]$
输出: 按照递增顺序排列的数组 $A$
算法步骤:

1. if $p < r$
2. then $q \leftarrow \left \lfloor\frac{p+r}{2} \right \rfloor$
3. $\quad MergeSort(A, p, q)$
4. $\quad MergeSort(A, q+1, r)$
5. $\quad Merge(A, p, q, r)$

MergeSort 函数使用了递归调用的方式, 也调用了Merge 过程。

小结

用伪码表示算法

• 伪码不是程序代码, 只是给出算法的主要步骤
• 伪码中有哪些关键字?
• 伪码中允许过程调用

第六节：函数渐进的界

大 $O$ 符号

定义: 设 $f$ 和 $g$ 是定义在自然数集上的函数, 若存在正常数 $c$ 和 $n_0$, 使得对于一切 $n ≥ n0$ 都有 $0 ≤ f(n) ≤ c \cdot g(n)$, 成立时, 即称 f(n) 的渐近的上界是 $g(n)$, 记作 $f(n) = O(g(n))$。

大 $\Omega$ 符号

定义: 设 $f$ 和 $g$ 是定义在自然数集上的函数, 若存在正常数 $c$ 和 $n_0$, 使得对于一切 $n ≥ n_0$ 都有 $0 ≤ c \cdot g(n) ≤ f(n)$, 成立时, 即称 $f(n)$ 的渐近的下界是 $g(n)$, 记作 $f(n) = \Omega(g(n))$ 。

小 $o$ 符号

定义: 设 $f$ 和 $g$ 是定义在自然数集上的函数, 若对于任意正常数 $c$都存在 $n_0$，使得对一切 $n ≥ n_0$, 都有 $0 ≤ f(n) < c\cdot g(n)$ 成立时, 则记作 $f(n) = o(g(n))$

小 $\omega$ 符号

定义: 设 $f$ 和 $g$ 是定义在自然数集上的函数, 若对于任意正常数 $c$ 都存在 $n_0$，使得对一切 $n ≥ n_0$ 都有 $0 ≤ c \cdot g(n) < f(n)$ 成立，则记作 $f(n) = \omega(g(n))$ 。

$\Theta$ 符号

定义: 设 $f$ 和 $g$ 是定义在自然数集上的函数, 若 $f(n) = O(g(n))$ 且 $f(n) = \Omega(g(n))$, 则记作 $f(n) = \Theta(g(n))$ 。

说明:

1. $f(n)$ 的阶与 $g(n)$ 的阶相同
2. 可以对于前面有限个 $n$ 不满足条件

小结

五种函数增长的符号
如何用定义证明函数的阶

第七节：有关函数渐进界的定理

定理1

定理：设 $f$ 和 $g$ 是定义域为自然数集合的函数。

1. 如果 $\lim_{n \to \infty} \frac{f(n)}{g(n)}$ 存在，并且等于某个常数 $c > 0$，那么 $f(n) = \Theta(g(n))$。
2. 如果 $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$，那么 $f(n) = o(g(n))$。
3. 如果 $\lim_{n \to \infty} \frac{f(n)}{g(n)} = +\infty$，那么 $f(n) = \omega(g(n))$。

定理2

定理：设函数 f、g、h 的定义域为自然数集合，

1. 如果 $f=O(g)$ 且 $g=O(h)$，那么 $f=O(h)$。
2. 如果 $f=\Omega(g)$ 且 $g=\Omega(h)$，那么 $f=\Omega(h)$。
3. 如果 $f=o(g)$ 且 $g=o(h)$，那么 $f=o(h)$。

函数的阶之间的关系具有传递性。

定理3

定理：假设函数 $f$ 和 $g$ 的定义域为自然数集合, 若对某个函数 $h$, 有 $f=O(h)$ 和 $g=O(h)$，那么 $f+g=O(h)$。

该性质可以推广到有限个函数。算法中有限步骤构成。若每一步的时间复杂度函数的上界都是 $h(n)$，那么该算法的时间复杂度函数可以写作 $O(h(n))$。

第八节：几类重要的函数

基本函数类

阶的高低：至少指数级、多项式级、对数多项式级

Stirling公式：$n! = \sqrt{2\pi n} \cdot \left(\frac{n}{e}\right)^n \cdot (1 + \Theta(\frac{1}{n}))$

重要结论:

• $n! = o(n^n)$
• $n! = \omega(2^n)$
• $n! = \Theta(n^n)$
• $\log n! = \Theta(n \log n)$

$$\begin{align*} C^m_{m+n-1} & = \frac{(m + n-1)!}{m!(n-1)!} \\ & = \frac{\sqrt{2\pi(m+n-1)}\cdot (m+n-1)^{m+n-1}(1+\Theta(\frac{1}{m+n-1}))}{\sqrt{2\pi m }\cdot m^m(1+\Theta(\frac{1}{m}))\cdot \sqrt{2\pi(n-1)} \cdot (n-1)^{n-1}(1+\Theta(\frac{1}{n-1})) } \\ & = \frac{\sqrt{2\pi(m+n-1)}\cdot (m+n-1)^{m+n-1}}{\sqrt{2\pi m }\cdot m^m\cdot \sqrt{2\pi(n-1)} \cdot (n-1)^{n-1}} \\ & = \Theta((1+\varepsilon)^{m+n-1}) \end{align*}$$