最小生成树

Prim算法

Kruskal算法

单源最短路径及算法

本文继续介绍重要的贪心算法，比如哈夫曼编码、最小生成树等算法。

最优前缀码及哈夫曼编码

二元前缀码

二元前缀码：用0-1字符串作为代码表示字符，要求任何字符的代码都不能作为其它字符代码的前缀。

非前缀码的例子：

a: 001, b: 00, c: 010, d: 01

解码的歧义，例如字符串0100001

• 解码1：01,00,001 $\implies$ d,b,a

• 解码2：010,00,01 $\implies$ c,b,d

本文开始记录贪心算法的学习。

贪心算法的例子——活动选择问题

输入：$S=\{1,2,...,n\}$为$n$项活动的集合，$s_i$、$f_i$分别为活动$i$的开始和结束时间。

活动$i$ 与$j$相容 $\iff s_i \ge f_j$ 或 $s_j \ge f_i$

求：最大的两两相容的活动集$A$

卷积及其应用

向量计算

给定向量：

• $a=(a_0, a_1, ..., a_{n-1})$

• $b=(b_0, b_1, ..., a_{n-1})$

向量和： $a+b=(a_0+b_0,a_1+b_1,...,a_{n-1}+b_{n-1}$

幂乘问题

输入：$a$为给定实数，$n$为自然数

输出：$a^n$

传统算法思想

顺序相乘 $a^n=(...(((a\quad a)a)a)...)a$

乘法次数：$\varTheta (n)$

基础思想

• 用首元素$x$作划分标准，将输入数组$A$划分成不超过$x$的元素构成的数组$A_L$，大于$x$的元素构成的数组$A_R$。其中，$A_L,A_R$从左到右存放数组$A$的位置。

• 递归地堆子问题$A_L$和$A_R$进行排序，直到子问题规模为$1$时停止。

减少子问题数

依据

分治算法的时间复杂度方程

$W(n) = aW(n/b) + d(n)$

$a$：子问题数，$n/b$：子问题规模，$d(n)$：划分与综合工作量。

算法设计思想

• 将原问题归结为规模为n-1的2个子问题；

• 继续归约，将原问题归结为规模为n-2的4个子问题。继续…，当子问题规模为1时，归约过程截止。

• 从规模1到n-1，陆续组合两个子问题的解。直到规模为n。

• 分析方法：递推方程。

基础思想

分治策略(Divide and Conquer)基本思想：

1. 将原始问题划分或者归结为规模较小的子问题；

2. 递归或迭代求解每个子问题；

3. 将子问题的解综合得到原问题的解。

选择问题

选最大和最小

输入：集合$L$（含$n$个不等的实数）

输出：$L$中的第$i$小的元素

• $i=1$，称为最小元素

• $i=n$，称为最大元素

位置处在中间爱你位置的元素，成为中位元素。

$n$为奇数，中位数唯一，$i=(n+1)/2$。

$n$为偶数，可指定为$i=n/2+1$。

选最大算法：顺序比较，在最坏情况下的时间为$W(n)=n-1$。

数列求和公式

1. 函数渐近界的定理

   • 定理1

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

     （1）如果$\lim\limits_{n\rightarrow\infty}f(n)/g(n)$存在，并且等于某个常数$c>0$，那么$f(n)=\Theta(g(n))$。

     （2）如果$\lim\limits_{n\rightarrow\infty}f(n)/g(n)=0$，那么$f(n)=o(g(n))$。

     （3）如果$\lim\limits_{n\rightarrow\infty}f(n)/g(n)=+\infty$，那么$f(n)=\omega(g(n))$。

     推理1 → 多项式函数的阶低于指数函数的阶，$n^d=o(r^n),r>1,d>0$。

     推理2 →对数函数的阶低于幂函数的阶，$\ln n=o(n^d),d>0$。