最小生成树

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

Temporal data structures:

• persistent data structures

  保存过去状态的全部信息。

• retroactive data structures

The Pointer Machine Model

A pointer machine is an “atomistic” abstract computational computational machine model akin to the random-access machine.

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

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

输入：$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$。

图论作为数学领域的重要分支已经有数百年的历史。图论应用的领域广泛，包括了地图、网页信息、电路、任务调度、商业交易、计算机网络和社交网络等。