0%

算法上课内容总结

LEC 1 概述

解决问题的三要素:输入 输出 算法

数据结构

输入、输出与数据结构直接相关。

数据结构时数据之间的逻辑关系、数据在计算机上的存储方式、数据的操作。

数据结构与算法设计是密切相关的。

算法

算法是为了求解问题而给出的指令序列。

一般特性

正确性
有效性
确定性
有穷性

算法效率

计算时间
存储空间
网络带宽

LEC 2 算法渐进分析

一般我们不必花大力气算出算法的精确运行时间,我们关心的是在大规模的输入下,算法的运行时间是如何随着输入规模的增大而变化的。此时,我们可以忽略低阶项和常量,使用渐进分析。
开销函数的估计是相对的而不是绝对的,开销函数的阶的增长决定了开销的大小。

渐进符号

$O$ 渐进上界
$Ω$ 渐进下界
$Θ$ 渐进紧确界

分析实例

矩阵求和

$O(n)$ $n=k^2$ (k 为矩阵维度)

插入排序

最好 O(n) 最坏 O(n^2)

合并排序

$O(nlgn)$

LEC 3 递归关系

许多算法,时间开销函数都可以用递归关系来描述。

置换法

猜想出一个表达式,验证表达式的正确性。

递归树

将迭代过程展成树的形式,分析树的每一层的消耗,然后求和。

迭代法

根据迭代公式,利用数学方法求解。

主方法

主方法依赖如下的主定理:

可以根据主定理方便求解效率,但有真空地带。

LEC 4 线性时间的排序法

基于比较的排序的开销下限

这一节先分析了基于比较的方法的排序的开销下限,我们通过判定树模型证明下限为$nlgn$。要打破这个下限,就要寻找非比较的排序方法,即:

计数排序

基本思想是排序指定范围内(0~k)的数,使用大小分别为n、k、n的数组a、b、c。根据 c 中小于 x 的个数,将元素放到 b 的指定位置。

基数排序

基本思想是根据数字每一位的大小进行排序。

桶排序

基本思想是将待排序元素放入桶中,每个桶分别排序,桶之间保持顺序。

LEC 5 分治法

分治法的思想,将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归时的三个步骤:

分解步骤将问题划分为一些子问题,子问题的形式与原问题一样,只是规模更小。

解决步骤递归的求解子问题,如果子问题的规模足够小,则停止递归直接求解。

合并步骤将子问题的解组合成原问题的解。

应用

二分搜索

归并排序

最大子数组问题

矩阵乘法的 Strassen 算法

Strassen 算法的运行时间的递归式为:

$T(n)=7T(n/2)+Θ(n^2)$

这里 a=7,b=2,$f(n)=Θ(n^2)$,即$n^{log_ba}=n^{log_27}$。存在ε=0.8有$f(n)=O(n^{lg7-ε})$。符合主定理的情况1,则$T(n)=Θ(n^{lg7})$。

最近点对算法

最近点对算法的递归式为:

$T(n)=2T(n/2)+O(n)$

这里 a=2,b=2,$f(n)=O(n)$,即$n^{log_ba}=n^{log_22}=n$。符合主定理的情况2,则$T(n)=O(nlgn)$。

LEC 6 随机化算法

雇佣关系

快速排序

随机化算法的分类

Las Vegas 算法 :总能给出正确的解或者无解。

Monte Carlo 算法 :大多数给出正确解,错误率可以控制在一定程度上。

如检查两个长串是否相同,直接比较为 Las Vegas 算法,验证指纹则为 Monte Carlo 算法。

LEC 7 统计算法

LEC 8 动态规划

简介

动态规划(dynamic programming),这里的 programming 不是编程的意思,而是表格的意思,意味着将求出的子问题的解存到表格中,以便下次用到时直接查表取出。动态规划与分治法类似,都是通过组合子问题的解来求解原问题。是典型的以空间换取时间的时空权衡的例子。

原理

适合用动态规划求解的问题的两个要素:最优子结构子问题重叠

步骤

动态规划求解的一般步骤:

(1)刻画一个最优解的结构特征。

(2)递归地定义最优解的值。

(3)计算最优解的值,通常采用自底向上的方法。

(4)利用计算出的信息构造一个最优解。

应用

动态规划有着很规范的范式,一般按照步骤来。

最长公共子序列

刻画最长公共子序列的特征

我们很容易用“剪切-粘贴”技术证明:两个序列的 LCS 包含这两个序列前缀的 LCS。即 LCS 问题拥有最优子结构。

一个递归解

计算 LCS 的长度

我们使用两个表 c 和 b。

Snipaste_2020-05-05_18-20-06

构造 LCS

沿着表 b 的箭头方向,从右下角开始,打印出公共元素即可。

作业排程

钢条切割

矩阵链乘法

矩阵链乘法就是寻找一个最优括号化方案,使得需要的标量乘法计算次数最少。

最优括号化方案的结构特征

最优括号化方案拥有最优子结构,我们可以使用“剪切-粘贴”方法很容易得证明,最优括号化方案包含其子链的最优括号化方案。

一个递归求解方案

计算最优代价

伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
MATRIX-CHAIN-ORDER(p)
n = p.length-1
let m[1..n 1..n] and s[1..n-1,2..n] be new table
for i = 1 to n
m[i,i] = 0
for l = 2 to n
for i = 1 to n-l+1
j = i+l-1
m[i,j] = ∞
for k = i to j-1
q = m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j]
if q < m[i,j]
m[i,j] = q
s[i,j] = k
return m and s

构造最优解

设计一个算法输出括号化方案。

LEC 9 贪心算法

简介

贪心算法和动态规划算法一样,通常用来求解最优化问题

贪心算法的思想是每一步都选择局部最优解,很多时候这种方法能得到最优解,而且速度比动态规划快很多,也更简单。

原理

并没有确定的方法简单证明一个问题是否适用贪心算法。

贪心选择性质最优子结构是两个关键要素。

步骤

(1)将最优化问题转化为这样的形式:对其做出一次选择后,只剩下一个子问题需要求解。

(2)证明作出贪心选择后原问题总是存在最优解。即贪心选择总是安全的。

(3)证明做出贪心选择后剩余的子结构满足性质:其最优解与贪心选择组合即可得到原问题的最优解,这样就得到了最优子结构。

应用

活动选择问题

霍夫曼编码

最小生成树

单源最短路径的 Dijkstra 算法

LEC 10 图算法

图的表示和存储方式

邻接链表 邻接矩阵

邻接链表因为在表示稀疏图时非常紧凑而成为通常的选择。

在稠密图的情况下,我们可能倾向于使用邻接矩阵表示法。快速判断任意两个节点之间是否有边相连,可能也需要使用邻接矩阵表示法。

LEC 11 最小生成树

LEC 12 单源最短路径

单源最短路径

单源最短路径问题是从源结点到其它结点的最短路径问题。

一般解决方案是 Bellman-Ford 算法,其允许负值权重的边。当存在负值环路时,算法返回不存在问题的解,否则返回最短路径及权重。思想是通过松弛操作逐渐降低权重。

还有著名的 Dijkstra 算法,其要求所有边的权重都为非负。其利用了贪心算法的思想,每次都选择最短路径。

LEC 13 全成对最短路径

全点对最短路径

全点对最短路径问题是从任一结点到其余结点的最短路径的问题。

如果不存在负值权重的边,可以用 Dijkstra 算法对每个结点进行操作。

还有一种利用动态规划思想的 Floyd-Warshall 算法,其要求可以存在负值权重的边,但不可以存在负值回路。