算法总结

这是个课程总结.

1. 分治法

适用条件

1. 原问题可以分解为若干个与原问题性质相类似的子问题
2. 问题的规模缩小到一定程度后可方便求出解
3. 子问题的解可以合并得到原问题的解
4. 分解出的各个子问题应相互独立，即不包含重叠子问题

基本步骤

1. 分解问题(divide)：把原问题分解为若干个与原问题性质相类似的子问题
2. 求解子问题(conquer)：不断分解子问题直到可方便求出子问题的解为止
3. 合并子问题的解(combine)：合并子问题的解得到原问题的解

相关算法

1. 归并排序

• 最好情况: $O(nlogn)$
• 最坏情况: $O(nlogn)$

2. 快速排序

• 最好情况: $O(nlogn)$
• 最坏情况: $O(n^2)$ (相同元素, 或者已经有序)

2. 动态规划

必要前提

1. 最优子结构性质: 一个问题的最优解中所包含的所有子问题的解都是最优的
2. 重叠子问题: 不是必要前提, 但存在重叠子问题可以提高算法效率

基本步骤

1. 确定问题的最优子结构
2. 递归定义最优解值
3. 自底向上计算最优解值
4. 从已计算得到的最优解值信息中构造最优解

相关算法

1. 矩阵链乘法 $O(n^3)$
2. 最长公共子序列问题 $Θ(mn)$, m,n为两序列长度
3. 最优二叉查找树 $O(n^3)$

3. 贪心算法

必要前提

1. 最优子结构性质: 局部最优+一系列贪心选择产生原问题的一个最优解
2. 贪心选择性质: 所求问题的最优解可以通过一系列局部最优的贪心选择而得到。即：局部最优->全局最优. 贪心选择性质是区别与动态规划方法的一个重要特征, 因为贪心法在作出选择时并不依赖于将来的情况, 只需根据当前的情况即可作出选择。

基本步骤

1. 确定问题的最优子结构
2. 将优化问题转化为作出一种选择，即贪心选择
3. 贪心选择后应只留下一个子问题，其它子问题均为空
4. 证明贪心选择的正确性，即本次贪心选择与剩余子问题的最优解可以构成原问题的最优解

贪心算法与动态规划的比较

1. 贪心法效率更高，表现在子问题不需要都计算，而选择数为1。
2. 动态规划方法的应用面更广，问题只需具有最优子结构即可，而贪心法不仅需要具有最优子结构性质，还需要具有贪心选择性质

相关算法

1. 活动选择问题(Recursive-Activity-Selector) $O(n)$
2. Huffman编码: 采用二叉堆管理序列, $O(nlgn)$

胚的概念

• 胚$(S, I)$, $S$是有限集, $I$是$S$的独立子集构成的集合族:
  • 独立性: 每个独立集的子集也是独立的. 即任何${A’} \subseteq A \subseteq S$, 如果 $A \in I$, 则 ${A’} \in I$
  • 交换性: 如果$A$和$B$是$I$的两个独立集，$A$比$B$有更多的元素, 则在$A$中存在一个元素，当其加入$B$时得到一个比$B$更大独立集.
• 最大独立子集: 若$A$是$S$的独立子集即$A \in I$, 如果存在一个元素$x \notin A$, 且 $A \cup \lbrace x \rbrace \in I$, 则称为$A$的一个扩展. 如果A不存在扩展就称为最大独立子集
• 加权胚: 为$S$中每个元素$x$赋予一个权重$w(x)$, 对于集合$A$, 其中每个元素乘以各自的权重得到的就是$A$的权值, 即: $$w(A) = \sum\limits_{x \in A} w(x)$$
• 最优子集: 使$w(A)$权值达到最大的独立子集A称为最优子集. 若$A$是$S$的独立子集, 由于任何元素$x \in S$的权重$\omega(x)$都是正数, 故最大独立子集具有最大权重, 最优子集 = 最大独立子集

4. 渐进记号

• $f(n) = O(g(n))$: $g(n)$是$f(n)$的上界
• $f(n) = \Omega(g(n))$: 下界
• $f(n) = \Theta(g(n))$: 紧确界
• $f(n) = \omicron(g(n))$: 不紧确上界
• $f(n) = \omega(g(n))$: 不紧确下界

5. 主方法

$T(n) = a T(n/b) + f(n)$ 比较$n^{log_b a}$和$f(n)$:

• 情况1: $f(n) = O(n^{log_b a})$, $T(n) = \Theta(n^{log_b a})$
• 情况2: $f(n) = \Theta(n^{log_b a})$, $T(n) = \Theta(n^{log_b a} lgn)$
• 情况3: $f(n) = \Omega(n^{log_b a})$, 且对某个常数c<1存在足够大的n使得$a f(n/b) \leq cf(n)$, 则$T(n) = \Theta(f(n))$

6. 红黑树

二叉查找树

1. 假设n为节点数, h为树高, 则h最低为$lg(n)$, 最高为n
2. 静态操作: 查找结点、找前驱、后继等时间为O(h)
3. 动态操作: 插入和删除结点等时间为O(h)

红黑树

1. 查找、插入、删除: O(h)
2. 插入最多旋转2次, 删除最多旋转3次

序统计树

定义: 所谓序统计就是在一系列数中找出最大、最小值，某个数的序值等操作

1. 找第i个最小值操作: O(lgn)
2. 求x的序值操作: O(lgn)
3. 插入或删除操作: O(lgn)

区间树

1. i与i’重叠可描述为: $low[i]≤high[i’], low[i’] ≤high[i]$
2. 插入和删除操作: O(lgn)

数据结构扩张的步骤

1. 挑选一个合适的基本数据结构
2. 决定在基本数据结构上应增加的信息
3. 修改基本数据结构上的操作并维持原有的性能
4. 修改或设计新的操作

7. 平摊分析

####势函数方法 先证明势函数恒为正, 再计算平摊代价

1. 栈操作
2. 二进制计数器
3. 动态表扩张/收缩

8. 二项堆

性质

1. 最小堆性质: 节点关键字大于父节点关键字
2. 没有度数相同的根. 使用二进制表示每个根, 那么每一位的大小就是结点个数, 因此n个结点最多有lgn+1颗二项树
3. 根表: 单链表, 根的度数严格递增

算法性能:

|算法|性能(最坏)|备注| |:-:|:-:| |建堆|O(1)| |寻找最小关键字|$\Omega(lgn)$|沿着根表寻找最小值| |合并两个二项堆|$\Omega(lgn)$|维护两个指针, 连接两个度数相同的根,跳过三个度数相同的根里的第一个| |插入节点|$\Omega(lgn)$|先构造一个节点的二项堆,再合并| |抽取最小节点|$\Theta(lgn)$|删除根, 将子树逆序排列, 再与剩下的堆合并| |减少关键字的值|$\Theta(lgn)$|如果比父节点小就交换,直到比父节点大| |删除节点|$\Theta(lgn)$|先减少到最小, 再抽取最小节点|

9. 斐波那契堆

性质

1. 根表: 环形双链表, 指向最小值

算法性能