Advanced Algorithm Lecture1(高等算法笔记)

个人博客: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个数,对其进行排序。

解决排序的思路:

  1. 找到集合S中的中位数y
  2. 将S划分为小于y和大于y的两部分$S_1,S_2$
  3. 递归对$S_1$和$S_2$排序

计算复杂性:

  1. 找到集合S中的中位数y(cn)
  2. 将S划分为小于y和大于y的两部分$S_1,S_2$(n)
  3. 递归对$S_1$和$S_2$排序
    可以得到复杂性为:$T(n) <= 2T(n/2) + (c+1)n$

为什么快排没有这么做?

  1. 找中位数算法的时间复杂度cn中的c比较大,以前大约是20以上,现在可以优化到2左右
  2. 找中位数的算法编程上较为复杂

假如我们可以以更低的代价求出大小相近的$S_1$和$S_2$?很难做到,难度和直接找中位数差不多。

快排的思路:

  1. 寻找集合S中随机的一个数y (O(1))
  2. 将S划分为小于y和大于y的两部分$S_1,S_2$(n)
  3. 递归对$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. 随机选一条边
  2. 把这条边的的合并在一起
  3. 删除自环
  4. 重复1-3步,指导只有两个顶点
  5. 剩余的边组成的是一个候选的最小割
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$次

上一篇:leetcode 5. 最长回文子串 (Manacher's Algorithm)


下一篇:初识数据结构和算法