四.分治策略

四.分治策略

一.分治法的归并排序

分治法步骤

分解: 分解成若干个子问题

解决: 解决子问题,子问题足够小时候直接求解

合并: 合并子问题

归并排序算法分析

关键是合并(Merge)两个已排序的子序列

为何不需要单独排序算法,合并的时候,已经带有了比较操作,比如两个长度为1的子序列,合并他们等价于比较二者大小

合并的基本思路是通过两个下标,逐项比较.

同时可以加入一个无限大的哨兵元素表示到达子序列的末

Merge 代码的实现

Merge API图示

归并伪代码

Merge(A , p , q , r)
	n1 = q-p+1 (计算子序列n1长度)
	n2 = r-(q+1)-1 (计算子序列n2长度)

	Let L[1:n1+1] R[1:n2+1] become new arrays 
	(将两个子序列拷贝到缓冲区L(eft) R(ight)数组中)
	copy A[p:q] to L[1:n1]
	copy A[q+1:r] to R[1:n2]
	
	(设置哨兵元素,供接下来的比较标识行尾)
	L[n1+1] = infinite
	R[n2+1] = infinite
	
	init i1 = 1, i2 =1 ;(建立指针index)
	for(init k = p; k==r ; k++)
	{
		if L[i1]<R[i2] then { A[k]=L[i1]; i1++}
		else           then { A[k]=R[i2]; i2++}
	}

Copy

C++

归并排序Merge-Sort伪代码

Merge-Sort (A , p , r)
{
	if(p == r) then { return } (直接相当于排序好了)
	else
	{
		q =  ⌊ p+q/2 ⌋  (向下取整)
		Merge-Sort (A , p , q)
		Merge-Sort (A , q+1 , r)

		Merge(A,p,q,r)
	}
}

Copy

C++

Merge 代码细节分析

计算子序列n1长度 n2长度

将两个子序列拷贝到缓冲区L[1:n1+1] R[1:n2+1]数组中

设置哨兵元素到多余的缓冲区末尾,供接下来的比较标识行尾

循环比较,将缓冲区内容按顺序搬运A

二.最大和的连续子序列

问题简介

整数序列A1,A2...An,寻找求合值为大的序列

穷举法(遍历法)

算法分析

设index [i,j] 用两个循环分别遍历所有的可能,一共有Cn2C_n^2Cn2​﻿种可能

对每种可能求和并保存其中的最大值

算法复杂度分析(多层循环下的复杂分析示例)

若不保存子序列的结果,而是只记载最大的子序列,则有三层循环

两个index下标循环带来Ω(n2)\Omega(n^2)Ω(n2)﻿的下限

对于每个子序列,S1=n+(n−1)+...1S_1=n+(n-1)+...1S1​=n+(n−1)+...1﻿中,每一项代表外层循环的index不变(i) 内层循环的index变动

取S1S_1S1​﻿的第一项: 代表着i=1j=[1→n]i=1\quad j=[1→n]i=1j=[1→n]﻿ 对于每一对ij,内部需要j−ij-ij−i﻿次加法

S1S_1S1​﻿第一项nnn﻿变化为n+(n−1)+...1n+(n-1)+...1n+(n−1)+...1﻿,同理第二项变化为(n−1)+...1(n-1)+...1(n−1)+...1﻿

S总=∑i=1i=nΘ(i2)=Θ(n3)S_总 = \sum_{i=1}^{i=n} \Theta(i^2) =\Theta(n^3)S总​=∑i=1i=n​Θ(i2)=Θ(n3)﻿

复杂度分析经验法则: 对于多层循环,只需要考虑执行最多的语句即可,此处为最内层的加法执行语句

遍历法的简单优化-算法分析

[star t: end]子序列求和，可以由上一次求和[start : end-1]的结果加上[end]得到

只需要二层循环可以分析得到Θ(n2)\Theta(n^2)Θ(n2)﻿算法

也可将每个结果保存在一个二位数组中,通过最后再来遍历这个二位数组的结果

不只最大最小值

极度消耗空间,所有的情况仅为Cn2=Θ(n2)C_n^2=\Theta(n^2)Cn2​=Θ(n2)﻿ 如果非连续情况下有Cn0+Cn1+...=2nC_n^0+C_n^1+... =2^nCn0​+Cn1​+...=2n﻿情况无法分析

分治算法

算法分析

最大子数组位于A[low:mid]中→递归调用自身

最大子数组位于A[mid:high]中→递归调用自身

最大子数组横跨于数组的中间→执行Θ(n)\Theta(n)Θ(n)﻿的寻找最大子数组

则有T(n)=2T(n/2)+Θ(n)T(n)=O(nlg(n))T(n)=2T(n/2)+\Theta(n)\quad T(n) = O(nlg(n))T(n)=2T(n/2)+Θ(n)T(n)=O(nlg(n))﻿ 可通过主方法\递归树法证明

代码实现

Find-Max-Crossing-Middle-Subarray

Find-Max-CrossingMiddle-Subarray(A,low,mid,high)
{
	{
		查找左边[low:mid]最大子序列
		init left-point = mid 
		init left-sum = A[mid]
		init temp-sum = 0
			for i = mid->low
				temp-sum = sum + A[i]
				if temp-sum > left-sum then {left-sum = temp-sum, left-point = i}
	}
	{
		查找右边[low:mid]最大子序列,步骤一致忽略
	}
	{return left-point , right-point , right-sum + left-sum}
}

Copy

C++

Find-Maximum-Subarray

Find-Maximum-Subarray(A,low,high)
{
	if high == low then {return low,high,A[kow]}
	else
	{
		(left-low,left-high,left-sum) = Find-Maximum-Subarray(A,low,high+low/2)
		(right-low,right-high,right-sum) = Find-Maximum-Subarray(A,high+low/2,high)
		(mid-low,mid-high,mid-sum) = Find-Max-Crossing-Middle-Subarray
	}
	{比较三个的返回mid-sum,left-sum,right-sum , 选择最大的一组参数返回即可}
}

Copy

C++

三.带入法求解递归式

代入法(数学归纳法)简介

本质上是一种严谨验证解的形式

需要先猜测解,然后再带入解,利用数学归纳法

带入法示例

确定T(n)=2T(⌊n/2⌋)+nT(n)=2T(\lfloor n/2 \rfloor)+nT(n)=2T(⌊n/2⌋)+n﻿的上界,猜测T(n)=O(nlgn)T(n)=O(nlgn)T(n)=O(nlgn)﻿

则有T(n)≤2(c2n2lg(n2))+n≤cnlg(n/2)+n=cnlgn−cnlg2+n≤c2nlgnT(n)≤2(\frac{c}{2}\frac{n}{2}lg(\frac{n}{2}))+n≤cnlg(n/2)+n
\\
=cnlgn-cnlg2+n\leq c_2nlgnT(n)≤2(2c​2n​lg(2n​))+n≤cnlg(n/2)+n=cnlgn−cnlg2+n≤c2​nlgn﻿

证明原猜测成立

数学归纳法的注意事项

注意必须严格成立

不能说cnlgn−cnlg2+n=Θ(nlgn)cnlgn-cnlg2+n = \Theta (nlgn) cnlgn−cnlg2+n=Θ(nlgn)﻿所以成立

此处为数学归纳法证明,需要和归纳假设严格一致的形式,不能循环证明

数学归纳法的初始条件选择

我们需要证明的上界T(n)≤cnlgnT(n)≤cnlgn T(n)≤cnlgn﻿ 对于n0=1n_0=1n0​=1﻿不成立

但是渐进符号的定义也没有要求从n0=1n_0=1n0​=1﻿就要成立,我们可以手动选择的n_0

实际上,上述示例中n0=2n_0 = 2n0​=2﻿时候表达式即成立了

猜测解的选择技巧

考虑n取非常大的情况

比如示例T(n)=2T(⌊n/2⌋+17)+nT(n)=2T(\lfloor n/2 \rfloor+17)+nT(n)=2T(⌊n/2⌋+17)+n﻿

当n非常大时候 +17可以被忽略,于是结果还是T(n)≤cnlgnT(n)≤cnlgnT(n)≤cnlgn﻿

猜测解通过加减低阶项实现证明

考虑T(n)=T(⌊n/2⌋)+T(⌈n/2⌉)+1 T(n)=T(\lfloor n/2 \rfloor)+T(\lceil n/2 \rceil)+1T(n)=T(⌊n/2⌋)+T(⌈n/2⌉)+1﻿ 猜测解为T(n)≤cnT(n)≤cnT(n)≤cn﻿

带入则有T(n)≤⌊cn/2⌋+⌈cn/2⌉+1≤cn+1T(n) \leq \lfloor cn/2 \rfloor + \lceil cn/2 \rceil +1 \leq cn+1T(n)≤⌊cn/2⌋+⌈cn/2⌉+1≤cn+1﻿ 和猜测解不严格一致

但是发现只相差一个低阶项,高阶项的系数是正确的

不妨假设T(n)≤cn+dT(n)≤cn+dT(n)≤cn+d﻿ 带入即可解决问题

变量代换解决问题

求解 T(n)=2T(⌊n⌋)+lgnT \left( n \right) = 2 T \left( \lfloor \sqrt { n } \rfloor \right) + l g nT(n)=2T(⌊n​⌋)+lgn﻿ 可通过 令m=lgnm=lgnm=lgn﻿

变换为 T(2m)=2T(2m/2)+mT \left( 2 ^ { m } \right) = 2 T \left( 2 ^ { m / 2 } \right) + m T(2m)=2T(2m/2)+m﻿ 再令 S(m)=T(2m)S(m)=T(2^m)S(m)=T(2m)﻿

得到S(m)=2S(m/2)+mS(m) = 2S(m/2) + mS(m)=2S(m/2)+m﻿

四.递归树法求解递归式

代入法的问题: 

代入法可以简洁的证明一个递归式的猜测解,但本身无法得到猜测解

此时可以用递归树方法解决,但是要忍受一些不精确

对于任意的T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n)T(n)=aT(n/b)+f(n)﻿ 一些参数定义

递归树示意图

从第0层到第M层,一共M+1层

M=log⁡bnM= \log_{b}{n}M=logb​n﻿

summ=amf(n/bm)um_m = a^mf(n/b^m)umm​=amf(n/bm)﻿ 用m表示具体第几层,M表示m的最大层

T(n)=3T(n/4)+cn2T(n) = 3T(n/4) + cn^2T(n)=3T(n/4)+cn2﻿ 例子

五.主方法求解递归式

递归树示意图

主方法内容

T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n)T(n)=aT(n/b)+f(n)﻿ 其中n/b解释为⌈n/b⌉\lceil n/b \rceil⌈n/b⌉﻿或⌊n/b⌋\lfloor n/b \rfloor⌊n/b⌋﻿

比较f(n)f(n)f(n)﻿ 和 nlog⁡ban^{\log_{b}{a}}nlogb​a﻿ 渐进大小区别

f(n)=O(nlog⁡ba−ϵ)⇔f(n)≤Onlog⁡ba−ϵ⇒T(n)=Θ(log⁡ba)f(n) = O(n^{\log_{b}{a-\epsilon}}) \Leftrightarrow f(n) \overset{O}{\leq}n^{\log_{b}{a-\epsilon}} 

\Rightarrow T(n) = \Theta(\log_{b}{a}) f(n)=O(nlogb​a−ϵ)⇔f(n)≤O​nlogb​a−ϵ⇒T(n)=Θ(logb​a)﻿ 

f(n)=Ω(nlog⁡ba+ϵ)⇔f(n)≥Ωnlog⁡ba+ϵ⇒T(n)=Θ(f(n))f(n) = \Omega(n^{\log_{b}{a+\epsilon}}) \Leftrightarrow f(n) \overset{\Omega}{\geq}n^{\log_{b}{a+\epsilon}} 

\Rightarrow T(n) = \Theta(f(n))f(n)=Ω(nlogb​a+ϵ)⇔f(n)≥Ω​nlogb​a+ϵ⇒T(n)=Θ(f(n))﻿

f(n)=Θ(nlog⁡ba)⇔f(n)=Ωnlog⁡ba⇒T(n)=Θ(nlog⁡ba∗lg⁡n)f(n) = \Theta(n^{\log_{b}{a}}) \Leftrightarrow f(n) \overset{\Omega}{=}n^{\log_{b}{a}} 

\Rightarrow T(n) = \Theta(n^{\log_{b}{a}}*\lg{n} 
)f(n)=Θ(nlogb​a)⇔f(n)=Ωnlogb​a⇒T(n)=Θ(nlogb​a∗lgn)﻿

我法-主定理证明

即求 ∑i=0i=Maif(nbi)\sum\limits_{i=0}^{i=M}a^if(\frac{n}{b^i})i=0∑i=M​aif(bin​)﻿ 

当f(n)=nkf(n) = n^k f(n)=nk﻿时候

求和证明

\sum\limits_{i=0}^{i=M}(\frac{a}{b^k})^i n^k = n^k (\frac{ 1-(\frac{a}{b^k})^{M+1}}{1-\frac{a}{b^k}}) ---(等比数列求和)\\ = n^k (\frac{1-(\frac{a}{b^k})^{\log_{b}{n}+1}}{1-\frac{a}{b^k}})\\ = n^k (\frac{1-(\frac{a^{M+1}}{b^{k(M+1)}})}{1-\frac{a}{b^k} })\\ 且有b^{kM} = b^{k\log_{b}{n}} = n^k \\ 且有a^{\log_{b}{n}}=a^{\frac{\log_{a}{n}}{\log_{a}{b}}} = n^{\log_{b}{a}} \\ = n^k (\frac{1-(\frac{a*n^{\log_{b}{a}}}{b^k*n^k})}{1-\frac{a}{b^k} }) \\ = (\frac{n^k-(\frac{a*n^{\log_{b}{a}}}{b^k})}{1-\frac{a}{b^k} })\\

可以看见分母,关键是比较 nk即f(n)和nlog⁡ban^k 即f(n) 和 n^{\log_{b}{a}} nk即f(n)和nlogb​a﻿ 的渐进大小 

问题1: 当二者渐进相等的时候,本求和无法说明为何T(n)=Θ(nlog⁡ba∗lg⁡n)T(n) = \Theta(n^{\log_{b}{a}}*\lg{n} )T(n)=Θ(nlogb​a∗lgn)﻿

解决,当二者渐进相等,每一项(abk)ink=(ablog⁡ba)ink=1ink=f(n)(\frac{a}{b^k})^i n^k = (\frac{a}{b^{\log_{b}{a}}})^i n^k = 1^i n^k =f(n)(bka​)ink=(blogb​aa​)ink=1ink=f(n)﻿ 均为f(n)f(n)f(n)﻿ 不再可以使用等比求和公式替代,直接f(n)∗层数f(n)*层数f(n)∗层数﻿即可

标准证明方法