算法设计技巧与分析笔记

前言

​ 本来是觉得可以不用复习的angry bird还没写完呢，但是老师说全是大题还是有点慌 毕竟我不记得英文名啊，只写过代码

小小的按目录考点顺序总结一下。书在这里下载

​ 代码都是伪代码大概，还有些自己yy的抓题。

复杂度

这一部分单独提前提出来复习一下，不然后面算法要分析复杂度又提一遍。

• O：最坏复杂度
• $\Omega$：理想情况下最好的时间复杂度​
• $\Theta$：平均复杂度

​ 通常解题说的O是渐进时间复杂度，因为我们只关心最坏的时间复杂度能不能过这一题，而不是$ \Omega $，且因为最好情况没有实际意义。而$\Theta$、可能是因为打出来太麻烦导致人们不是很常用（其实我们平常口胡的复杂度含义更多是$\Theta$​），而且人们更喜欢一个确定的值故O更为常用 个人理解。

使用什么算法大概可以用以下依据判断:

每个阶段只有一个状态->递推；
每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；
每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。

重要推论

在推导复杂度或比较次数的时候会遇到很多形如下面的式子：

$$f(n) \begin{cases} d & \quad n=1\\ af(n/c)+bn &\quad n\geq2 \end{cases}$$

上述递推式的解为

$$f(n)= \begin{cases} bnlog_cn+dn & \quad a=c \\ (d+\frac{bc}{a-c})n^{log_c a}-\frac{bc}{a-c}n &\quad a\neq c \end{cases}$$

通常情况下c=a=2，所以通常复杂度是$bnlog_2n+dn$​

更通常情况：

$$f(n) \begin{cases} d & \quad n=1\\ af(n/c)+bn^x &\quad n\geq2 \end{cases}$$

的解是：

$$f(n)= \begin{cases} \Theta(n^x) \\ \Theta(n^xlog~n) \\ \Theta(n^{log_ca}) \\ \end{cases} =\begin{cases} bn^x & \quad a<c^x\\ O(n^{log_ca})logn &\quad a=c^x \\ O(n^{log_ca}) &\quad a>c^x \\ \end{cases}$$

O还是$\Theta$我也有点不确定

上面通解看似难实际上 就是比较递归部分和非递归部分的复杂度递归部分$O(n^{log_ca})$，非递归部分$bn^x$，

二分搜索(binary find)

没啥，最大比较次数$\lfloor{log n}\rfloor+1$​​​，因为一颗二叉树最大高度是$\lfloor log n\rfloor$​​

// a递增
l=1,r=n;
while l<=r
    mid=(l+r)/2;
    if a[mid]==x
    	return mid;
    else if a[mid]<x
    	l=mid+1;
	else
        r=mid-1;

容易被误导的例子

同时寻找数组中最大和最小的数。很容易被误导为二分，但是仔细一下发现必须遍历一遍所以复杂度不可能是O(log)而应是O(n)的

find(l,r)
    if r-l==1 // 用if可以实现只比较1次
        return min(a[l],a[r]),max(a[l],a[r])
    mid=(l+r)/2
    x1,y1=find(l,mid)
    x2,y2=find(mid+1,r)
    x=min(x1,x2)
    y=max(y1,y2)
    return x,y

递推式是：

$$f(n)= \begin{cases} 1 &\quad n=2 \\ 2*f(n/2)+2 & \quad n>2 \\ \end{cases}$$

算出比较次数为n/2+n-2

合并有序的两个列表(merge)

太简单，单独出大题不太可能。比较次数在$min(n_1，n_2) 到 n_1+n_2-1$​​​​​之间

// a[p,q] a[q+1,r]有序,从小到大合并
x=p,y=q+1
while x<=q && y<=r
	if a[x]<a[y]
		b[k]=a[x];
		x++
	else
		b[k]=a[y];
		y++;
	k++;
if x==q+1
	for i=y;i<=r;i++,k++
		b[k]=a[i]
else
	for i=x;i<=q;i++,k++
		b[k]=a[i]
	

选择排序(selection sort)

依次选出第k小，$O(n^2)$

for i=1;i<=n;i++;
	temp=i;
	for j=i+1;j<n;j++;
		if a[j]<a[temp]
			temp=j
	swap(a[i],a[temp])

算法比较次数为$\sum_1^{n-1}n-i=\frac{n(n-1)}{2}$，因为每次循环都会赋值三次，故赋值次数为0~3(n-1)​

插入排序(insertion sort)

从已经排好序的序列中寻找小于当前值的进行插入

for i=2;i<=n;i++
	x=a[i]
	j=i-1
    while j>0 && a[j]>x;
		a[j+1]=a[j]
         j--;
	a[j+1]=x;

最大比较次数：$\sum_{i=2}^n i-1=\frac{n(n-1)}{2}$，最小比较次数：n-1，元素赋值次数：比较次数+n-1​​

自底向上的排序(bottom up)

其实就是一个递归，只有两个元素的时候回溯(见下面的merge sort)，合并就是上面的merge

t=1

while t<n
	s=t,t=2*s,i=0;
	while i+t<=n
        // 分别对应p,q,r 
        // 每次合并[p,q],[q+1,r]
	    merge(i+1,i+s,i+t);
	    i+=t
    if i+s<n
        merge(i+1,i+s,n);

有观察结论：每次比较次数在$\frac{n}{2^j}2^{j-1}$​​​~$\frac{n}{2^j}(2^j-1)$​​​，级数求和可知最少比较次数为$\frac{nlog_2n}{2}$​​​最大比较次数为$nlog n-n+1$​​​。

算法分析

外层循环为$\lfloor log (n-1)\rfloor+1$​​​，现先假设n为二的幂，这样if语句不会被执行，外层循环log n次，里层的while执行为n/t次(注意t=2*s把t重新赋值了涉及到循环次数问题)，每次复杂度为O(merge):

当merge总是最小比较次数时：

$$f(t)=\frac{n}{t}*min(s,t-s-1+1)=n/t*s \\$$ $$\begin{aligned} f(n)&=\sum_{t=1}^{n-1} f(t)\\ ~~~~&=\sum_{i=1}^{k} \frac{n}{2^i}*\frac{2^{i}}{2} \\ ~~~~&= \frac{n}{2}logn \end{aligned}$$

当merge部分总是最大比较次数时：

$$f(t)=\frac{n}{t}*(s+t-s-1+1-1)=n/t*(t-1) \\$$ $$\begin{aligned} f(n)&=\sum_{t=1}^{n-1} f(t) \\ &=\sum_{i=1}^{k} \frac{n}{2^i}*(2^{i}-1) \\ &= nlogn-n\sum_{i=1}^k 2^{-i} \\ &= nlogn-n(1-\frac{1}{n}) \\ &= nlogn-n+1 \\ \end{aligned}$$

基数排序(radix sort)

这个伪代码比较好写

L={a0,a1,...an} 
for i in 1~k
	L0~L9=empty
	while L!=empty:
		a=L.font;
		L.pop;
		if j=a的第i位数字
			Lj.push a
	L=L0
	for i in 1~9
		L.push Li
print L

生成排列

方法1

似乎和书上的有些不同

如果有1~n-1的排列，则将n插入到每个排列的每个位置则可以得到1~n的排列。故从1开始到n+1结束（边界记得模拟一下）

for i=1;i<=n;i++
	p[i]=i;

perm(1)

perm m:
	if m==n print p[1~n]
	else
	for(int i=m;i<=n;i++)
		swap(p[m],p[i]);
		perm(m+1)
		swap(p[m],p[i]);

方法2

​ 排列就是n个数的自由组合，每一次选择一个数到下一个状态，知道每个数都选择完毕即可。

for(int i=1;i<=n;i++)
	use[i]=0;
perm(1)

perm m:
	if m==n+1 print use[1~n];
	for(int i=1;i<=n;i++)
		if use[i]==1
			continue;
         use[i]=m;
		perm(m+1);
		use[i]=0

复杂度是n*n!

算法分析

自己的yy

每太看懂书上递推的写法，自己yy的感觉没问题

$$f(m)= \begin{cases} n & m=n+1\\ (n-m+1)f(m+1) & 1<=m<=n \end{cases}$$

递推:

$$f(1)=n*f(2)=n*(n-1)*f(3)=\dots=n!*f(n+1)=n*n!$$

书上的答案

$$f(m)= \begin{cases} 0 & m=0\\ mf(m-1)+n & m>=1 \ \end{cases}$$

令 $m!h(m)=f(m)[h(0)=0]$则有：

$$\begin{aligned} h(m)&=h(m-1)+\frac{n}{m!}\\ h(m)&=h(0)+\sum_{j=1}^m\frac{n}{j!}=n\sum_{j=1}^m \frac{1}{j!} \\ f(m)&=n*m!*\sum_{j=1}^m\frac{1}{j!}<2nm! \\ \end{aligned}$$

将n带入m则有$f(n)<2n*n!$

寻找多数元素

注意这里的多数元素是大于n/2的元素，并不是众数。

for(int i=1;i<=n;)
	c=a[i];
	count=1;
    for(int j=i+1;j<n,count>0;j++)
		if c==a[j]
			count++;
		else
			count--;
	i=j+1;
check(c) // 判断c是否真的大于n/2 因为可能存在 4 4 4 3 2 1 5这种序列
print c

合并排序(merge sort)

伪代码

当n为2的幂时，比较次数与bottomup相同，实际上无论从应用层面分析都说bottomup牛逼，只是merge sort代码更好看更好调试罢了。人们更容易看懂递归而不是迭代

mergesort l,r
	if l<r
        int mid =(l+r)/2
        mergesort(l,mid);   // f(n/2)
        mergesort(mid+1,r); // f(n/2)
        merge(l,mid,r); 	// n/2~n-1

复杂度计算

$$f_{min}(n)= \begin{cases} 0 \quad & n=1 \\ 2*f_{min}(n/2)+n/2 & n>=2\\ \end{cases} \\ f_{max}(n)= \begin{cases} 0 \quad & n=1 \\ 2*f_{max}(n/2)+n-1 & n>=2\\ \end{cases}$$

最后计算得比较次数为$nlogn/2$~$nlogn-n+1$之间，时间复杂度为$\Theta (nlogn)$，空间复杂度为$\Theta(n)$​

快速排序

个人觉得未增强的快排和merge sort差不多，就是合并的算法不一样罢了。

split 算法

选择一个初始区间，在for之后在区间内得到一个位置i，位置小于i的全部不大于a[l]，位置大于i的全部不小于a[l]。

并不保证前半部分和后半部分有序！！

split(l,r): //
	x=a[l]
	pos=l
	for (i=l+1;i<=r;i++)
		if a[i]<=x
			pos++
             if i!=pos
             	swap(a[i],a[pos])
    swap(a[l],a[pos])
    return a,pos

每次固定比较n-1次但可能不交换，故复杂度为O(n)

快排

因为根据split算法，已经将序列分为两个有序的部分，现在只需要执行分治的基本思想即可：

sort(a,l,r)
	w=split(l,r)
	sort(a,l,w-1)
	sort(a,w+1,n)

算法分析

假设需求是从小到大排序。

最坏情况

可见快排的分治不像buttomup sort那样非常稳定（永远都是分一半），所以最坏的情况是每次w=l+1，即序列每次都被分为sort(a,l,l)，sort(a,l+1,n)，这样则需要递归调用n次，而split比较次数是稳定的(n-1)，故最坏情况复杂度为:

$\sum_{i=1}^{n} i-1=\frac{n(n-1)}{2}=O(n^2)$

平均情况

考虑数字都是随机排列且没有重复。则每个数字被split后w位置随机：设f(m)代表区间长度为m时的快排比较次数

$$f(n)= \begin{cases} 0 & \quad n=1 \\ n-1+\frac{1}{n}\sum_{w=1}^{w=n} f(w-1)+f(n-w) & \quad n>1 \end{cases}$$ $$\begin{aligned} f(n)&=n-1+\frac{1}{n}\sum_{w=1}^{w=n} f(w-1)+f(m-w) \\ &=n-1+\frac{2}{n}\sum_{w=1}^{n}f(w-1) \\ \end{aligned}$$

变形则有：

$$\begin{cases} n*f(n)&=n*(n-1)+2\sum_{w=1}^{n}f(w-1) \\ (n-1)*f(n-1)&=(n-1)*(n-2)+2\sum_{w=1}^{n-1}f(w-1) \\ \end{cases} \rightarrow \\ \frac{f(n)}{n+1}=\frac{2(n-1)}{n(n+1)}+\frac{f(n-1)}{n}$$

令$D(n)=\frac{f(n)}{n+1}$，D(1)=0：

$$\begin{aligned} D(n)&=\sum_{i=1}^{n} \frac{2(i-1)}{i*(i+1)} \\ &=\sum_{i=1}^{n} \frac{4}{i+1}-\frac{2}{i} \\ &=\frac{4}{n+1}-4+\sum_{i=1}^{n} \frac{2}{i} \\ &=\frac{4}{n+1}-4+2\gamma+2ln(n) \\ &=2log(n)+\Theta(1) \\ &\approx 1.44log (n) \end{aligned}$$

所以$f(n)=\Theta(nlog(n))$​

排序算法总结

算法名称	平均比较次数	最好比较次数	最坏比较次数	是否稳定
选择排序	$\frac{n*(n-1)}{2}$	$\frac{n(n-1)}{2}$	$\frac{n(n-1)}{2}$	否
插入排序	$n^2$	$n-1$	$\frac{n*(n-1)}{2}$	是
冒泡排序	$n^2$​	$\frac{n(n-1)}{2}$​​	$\frac{n(n-1)}{2}$	是
radix sort	$nd$	$nd$	$nd$	是
bottomup sort	$nlog_2n$	$\frac{nlog_2n}{2}$	$nlog_2n-n+1$	是
merge sort	$nlog_2n$	$\frac{nlog_2n}{2}$	$nlog_2n-n+1$	是
quick sort	$nlog_2n$	$nlogn$	$n^2$	否

寻找第k小元素

伪代码

select(A,l,r,k)
{
	p=r-l+1;
	if p<44	// c
		sort(A)
		return A[k]
	q=p/5 将A分为五组
    将q组中的元素单独排序找出中项并得到中项集合M。
	mm=select(M,1,q,(q+1)/2) // f(n/5)
    // n         
	A1={a|a<mm}
	A2={a|a=mm}
	A3={a|a>mm}
    // f(0.7n)
	case:
		|A1|>=k
			return select(A1,1,|A1|,k);
		|A2|+|A1|>=k  // 一定在A2里面
			return mm;
		|A1|+|A2|<k // 一定在A3里面
			return select(A3,1,|A3|,k);
}

复杂度分析

由上伪代码可见，关键是0.7n是如何计算出来的。只考虑第一和第三种情况，不考虑之间返回mm，只考虑最坏情况:

显然该两种情况是对称的，故可以只计算A1或A3的规模，严格小于可以转换为n-A3’其中A3’为大于等于mm的数

故有：

$$|A1|<=>|A3|\leq n-\frac{3}{2} \lfloor{n/5}\rfloor \leq n-\frac{3(n-4)}{2*5}=0.7n+1.2$$

想办法去掉1.2的常数

假设$0.7n+1.2 \leq \lfloor{0.75n}\rfloor$ 当然这里0.75是可以随便设置的

$$0.7n+1.2 \leq 0.75*n-1=> \quad n>=44$$

当然，不等式放缩可以有别的方式，所以常数可能不一样

$$f(n)= \begin{cases} c1 \quad & n<C \\ f(n/5)+f(0.75n)+c_2n & n>= C \end{cases}$$

最长公子序列问题(LCS)

感觉dp的都不是很侧重讲啊。

伪代码

for int i=1;i<=n;i++
	l[i,1]=0;
for(int i=1;i<=m;i++)
	l[1,j]=0;
for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
		if a[i]==b[j]
			l[i][j]=l[i-1][j-1]+1;
		else
			l[i][j]=max(l[i-1][j],l[i][j-1]);

背包问题

for int i=1;i<=n;i++
	for(int j=0;j<=m;j++)
		f[i,j]=0
		
for(int i=1;i<=n;i++)
	for(int j=0;j<=m;j++)
		fp[i][j]=f[i-1][j]
		if j>=s[i]
			f[i][j]=max(f[i][j],f[i-1][j-s[i]]+v[i])

图论

两两间最短路

dijstra

for(int i=1;i<=n;i++)
	dis[i]=inf
	
while(!q.empty())
	temp=q.front()
	q.pop()
	for(i in temp的边)
		if i not in q
			if dis[i]>dis[temp]+length[i][temp]
				dis[i]=dis[temp]+length[i][temp]
				q.push(i)

krusal

将边从小到大排序得到E
tot=0
for(e in E)
{
    if find(e.l)!=find(e.r)
        tot++
      	fa[e.l]=find(e.r)
    if tot>=n-1
        break
}

prim

T={},x={1},y=V-{1}
while(y!={})
    (x,y)为最小权重边,x属于X，y属于Y
    X=X+{y}
    Y=Y-{y}
    T=T+(x,y)
        

三着色问题|八皇后问题

这两个本质都是染色问题，所以在一起分析。

伪代码

\\递归回溯
for i=1;i<=n;i++
	c[i]=0;
color(k):
    for i in color
        c[k]=i
        // check为 O(n)
        if check(c)全部着色且不冲突 return and print c；
        else
            if check(c)不冲突
                // 部分着色
                color(k+1)；
    return       

\\ 迭代回溯
for i in n:
	c[i]=0
while(k>=1)
	while(c[k]<color)
		c[k]++
		if check 全部着色且不冲突
			print c
			return
		else if check部分着色且不冲突
               k++
    end while
    c[k]=0
    k--
end while
    

复杂度分析

$$f(k)= \begin{cases} n \quad & k=1 \\ 3*f(k-1) & k>=2\\ \end{cases}$$

搜索剪枝他不香吗

网络流(了解步骤即可)

FF

如果流量是无理数，可能找不到解，如果流量收敛可能不是最优解

for 边u,v 属于E
	f(u,v)=0
	
while G中有一条增广路径 p
	delta=p的瓶颈流量
	for p中每条边u,v
		f(u,v)=f(u,v)+delta
	更新剩余图G

最短路径长度增广(Minimum path length augmentation)

初始化剩余图R<-G，层次图L
    
while t在L中
    while L中存在s到t的路径
        对每个路径分别求出瓶颈容量d
        该路径增值d
    	更新L
    end while 
    用剩余图更新L
end while

匈牙利

伪代码

初始化匹配M={0}
while G中存在自由节点x，y：
    设r为一个自由节点，从r开始搜索生成一个路径交替树T。
    if T是一条匈牙利树
    	G-=t
    if T中找到一条增广路m
        M+=m