个人博客:https://www.pig2earth.top/2020/05/02/高等算法笔记Lecture1/
课程主要内容
随机算法:如何分析随机算法的成功率
近似算法:近似算法的设计技巧
Big O Notation
一般用大O来衡量算法复杂度。
$f(n) = O(g(n)) \text{代表} \leqslant$
$f(n)=\Omega(g(n)) \text{代表} \geqslant$
证明$f(n)=\Theta(g(n))$,等价于证明$f(n)\geq(g(n))$且$f(n)\leq c\cdot g(n)$
排序问题
待排序集合S包含n个数,对其进行排序。
解决排序的思路:
- 找到集合S中的中位数y
- 将S划分为小于y和大于y的两部分$S_1,S_2$
- 递归对$S_1$和$S_2$排序
计算复杂性:
- 找到集合S中的中位数y(cn)
- 将S划分为小于y和大于y的两部分$S_1,S_2$(n)
- 递归对$S_1$和$S_2$排序
可以得到复杂性为:$T(n) <= 2T(n/2) + (c+1)n$
为什么快排没有这么做?
- 找中位数算法的时间复杂度cn中的c比较大,以前大约是20以上,现在可以优化到2左右
- 找中位数的算法编程上较为复杂
假如我们可以以更低的代价求出大小相近的$S_1$和$S_2$?很难做到,难度和直接找中位数差不多。
快排的思路:
- 寻找集合S中随机的一个数y (O(1))
- 将S划分为小于y和大于y的两部分$S_1,S_2$(n)
- 递归对$S_1$和$S_2$排序
快排平均复杂度求解思路:y是第k大的概率是一样的(k可能为1...n)据此可以列出递推式:
$T(n) = \sum_{k=1}^{n} \frac{1}{n}(T(k-1)+T(n-k)+n-1)$
所以
$T(n)=\frac{2}{n}(T(0)+T(1)+\cdots+T(n-1))+n-1$
作业:$T(n)=?$
这里其实有一个值得注意的点:
我们可以把快排的所需要的次数用一个关于n的函数表达出来:
$f(n)=f(X_n-1)+f(n-X_n)+n-1$。
这里需要注意的是,$X_n$其实是一个关于n的随机变量。
因此,求快排的时间复杂度实际上是在求$f(n)$的期望:
$T(n)=E(f(n))=E(f(X_n-1)+f(n-X_n)+n-1)$
由于期望的可加性:
$T(n)=E(f(n))=E(f(X_n-1))+E(f(n-X_n))+n-1$
接下来就可以得到:
$E(f(X_n-1)=\sum_{k=1}^n Pr(Xn=k)E(f(k-1)|X_n=k))$
接下来我们进行了一个假设:f(k-1)和$X_n=k$无关
方法2:
设置一个随机变量:$X_{ij}=1(i-th\text{会和}j-th\text{进行一次比较}),\text{否则}X_{ij}=0$
所以时间复杂度=$E(\sum_{1\leqslant i<j\leqslant n} X_{ij}))=\sum_{1\leqslant i<j\leqslant n} P_{ij}$
这一步利用了E的可加性,它不要求每个事件间是相互独立的。所以问题转换成了求解$P{ij}$。也就是第i大的元素和第j大的元素做比较的概率。
这里可以先从两个简单的求一下作为启发:$P_{i,i+1}$和$P_{1,n}$
$P_{i,i+1}=1$因为,假设除了$a_i$和$a_{i+1}$以外,所有的关系我们都知道。那么我们就会得到$a_1<a_2<\cdots<(a_i\text{和}a_{i+1})<\cdots<a_n$。不进行比较,我们永远也不知道$a_i$和$a_{i+1}$哪个大。所以这个比较是一定要做的。
$P_{1,n}=\frac{2}{n}$原因是:在快速排序的第一轮,我们肯定会把最小和最大的分到两个集合里面分别去求。此后,由于最大和最小的元素在两个集合里面,所以他们就再也没有机会进行比较了。此时$X_{1,n}=0$。因此,只有在第一轮才有可能比较最小和最大的数。其它情况都不可能。
第一轮,假设选取的数是第3小的,则会:
(1 2) | 3 | (4 .. n)
第1和第2小的在一个集合,后面的在一个集合
这种情况下1和n肯定不会被比较。
当选取的数是第2小到第n-1小的时候同理。
所以只有一种情况1和n会被比较,也就是1或者n被选为那个分割的数的时候。
所以$P_{i,j}$如何求?以i=3,j=7为例,看快排的过程一共有三种情况。
$P_{ij}=\frac{2}{j-i+1}$
第一轮,假设选取的数是第3小或者第7小的的,则会有三种可能:
最后求和,时间复杂度=$\sum_{1\leqslant i<j\leqslant n} P_{ij}=\sum_{1\leqslant i<j\leqslant n} \frac{2}{j-i+1}$
进一步推导得到:
$2\sum_{1\leqslant i<j\leqslant n-1} (\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n-i+1})=2\sum_{1\leqslant i<j\leqslant n-1}(H_{n-i+1}-1)$
这个函数正好是$\theta(nlogn)$
最小割
一个无向图G(V,E),选出一组最少的边,把整个图切成两个不连通的分量。
算法:
- 随机选一条边
- 把这条边的的合并在一起
- 删除自环
- 重复1-3步,指导只有两个顶点
- 剩余的边组成的是一个候选的最小割
orig
b - c
/ |
a |
\ |
d _ e
step1: 假设随机选到了a<->b这条边
ab - c
/ | |
| | |
\ | |
d __ e
step2: 假设随机选了ab<->c这条边
d
/ |
abc |
\ |
e
成功概率为多少?$O(\frac{1}{n^2})$
作业:$(1-\frac{1}{n2}){n^2}=\theta(1)$
实现的复杂度?单次需要$O(n2)$,想将成功率提高到一个常数,需要重复$n2$次