算法复习笔记（三）

分治策略

归并排序

递推关系

$$
T(n)=\begin{cases}
2T(n/2)+cn,\quad n>2 \\
c,\quad n=2
\end{cases}
$$

用归纳法可证：
$$
T(n)=O(nlogn)
$$

其他递推关系

$$
T(n)=\begin{cases}qT(n/2)+cn,\quad n>2 \\c,\quad n=2\end{cases}
$$

对于q>2，$T(n)=O(n^{log_2q})$

对于q=1，$T(n)=O(n)$
$$
T(n)=\begin{cases}2T(n/2)+cn^2,\quad n>2 \\c,\quad n=2\end{cases}
$$

$$
T(n)=O(n^2)
$$

计数逆序 $O(nlogn)$

Merge-and-Count(A,B)

维护一个Current指针指向每个表，初始化指向首元素
维护一个变量Count用于逆序的计数，初始为0
While两个表都不空
	令ai和bj是由Current指针指向的元素
	把这两个表中娇小的元素输出到表中
	If bj是较小的元素 then
		把Count加上在A中的剩余元素数
	Endif
	把较小元素选出的表中的Current指针前移
EndWhile
一旦一个表为空，把另一个表剩余所有元素加到输出中
返回Count和合并后的表

Sort-and-Count(L)

If这个表中有一个元素 then
	没有逆序
Else
	把这个表划分成两半
	A包含前n/2个元素
	B包含剩下的n/2个元素
	(rA,A)=Sort-and-Count(A)
    (rB,B)=Sort-and-Count(B)
    (r,L)=Merge-and-Count(A,B)
Endif
返回r=rA+rB+r以及排好序的L

最邻近点对

Closest-Pair(p1, …, pn) { 
    //O(n log n)
    Compute separation line L such that half the points are on one side and half on the other side.      
    //2T(n / 2)
	δ1= Closest-Pair(left half) 
    δ2= Closest-Pair(right half) 
    δ= min(δ1, δ2)
    //O(n) 
	Delete all points further than δ from separation line L
	//O(n log n)  改进时，通过预处理去掉这一步排序
    Sort remaining points by y-coordinate.
    //O(n)
	Scan points in y-order and compare distance between each point and next 7 neighbors. If any of these distances is less than δ, update δ.
	return δ.
}

上面算法的时间复杂度为$T(n)=O(nlog^2n)$

改进后时间复杂度为$T(n)=O(nlogn)$

Closest-Pair-Rec(Px,Py) {
    If |P|<=3 then 
    	进行简单穷举排序 
        //在这里按y坐标将点排序，方便下面直接对窄带内的点归并排序
    End if
        
	构造Qx,Qy,Rx,Ry(O(n)时间) 
    （q0*,q1*）=Closest-Pair-Rec(Qx,Qy) 
    （r0*,r1*）=Closest-Pair-Rec(Rx,Ry)
        
	Delta=min(d(qo*,q1*),（r0*,r1*）) 
    x*=集合Q中的点的大的x坐标 
    L={(x,y):x=x*} 
	S=P中与L相距在Delta之内的点集

    构造Sy(O(n)时间) 
    For每个点Sy中的点s, 计算从s到跟着Sy的7个点中每个点的距离 
    令s,s'是达到其中小距离的点对(O(n)时间)

    If d(s,s')<Delta then 
         Return (s,s') 
    Else if d(q0*,q1*)<d(r0*,r1*) then
        Return (q0*,q1*) 
    Else 
        Return（r0*,r1*） 
    End if
}

整数乘法

公式

$x=x_12^{n/2}+x_0$

$y=y_12^{n/2}+y_0$

$xy=2^nx_1y_1+2^{n/2}(x_1y_0+x_0y_1)+x_0y_0$

$=2^nx_1y_1+2^{n/2}((x_1+x_0)(y_1+y_0)-x_1y_1-x_0y_0)+x_0y_0$

把4个乘法变成3个.

Recursive-Multiply(x,y) [Karatsuba-Ofman]

令$x=x_12^{n/2}+x_0，y=y_12^{n/2}+y_0$，

计算$x_1+x_0，y_1+y_0$，

p=Recursive-Multiply($x_1+x_0，y_1+y_0$)

x1y1=Recursive-Multiply(x1,y1)

x0y0=Recursive-Multiply(x0,y0)

return $x_1y_12^n+(p-x_1y_1-x_0y_0)2^{n/2}+x_0y_0$

在两个n位因数上的运行时间是 $T(n)=O(n^{log_23})=O(n^{1.59})$

矩阵乘积 (Strassen)

P1=A11×(B12−B22)

P2=(A11+A12)×B22

P3=(A21+A22)×B11

P4=A22×(B21−B11)

P5=(A11+A22)×(B11+B22)

P6=(A12−A22)×(B21+B22)

P7=(A11−A21)×(B11+B12)

$C_{22}=A_{22}B_{2*2}$

C11=P 5+P4−P 2+P 6

C12=P1+P2

C21=P3+P4

C22=P5+P1−P3−P7

7 次乘法，18 = 10 + 8 次加减法

$T(n)=O(n^{log_27})=O(n^{2.81})$

类Strassen算法上每获得一点理论上的改进， 实际上的可用性就会降低。 （需要n达到一定规模，例：两个70×70分块矩阵乘法可以用143,640次向量乘法 ）

卷积与快速傅立叶变换

多项式

	系数表示	点值表示
求值	O(n) (采用Horner方法)	O(n^2)
加法	O(n) arithmetic operations	O(n) arithmetic operations
乘法(卷积)	采用直接算法O(n^2)	需要2n-1 个点 O(n)

系数表达到点值表达

把多项式表达分成奇偶部分。选择$x_k= ω^k$，其中ω是n次单位根。求$A(x) = a_0+ … + a_{n-1}x^{n-1}$在n次单位根$ω^0, ω^1, …, ω^{n-1}$处的值。

如果n是偶数，那么n/2次单位根可以表 示为$ν^0, ν^1, …, ν^{n/2-1}$，其中$ν= e ^{4πi / n}$.

$A(x) =A_{even}(x^2) + xA_{odd}(x^2)$. $A(-x) =A_{even}(x^2) - xA_{odd}(x^2)$.

分别计算多项式：

$A_{even}(x)$ ，$A_{odd}(x)$在$½n$th单位根$ν^0, ν^1, …, ν^{n/2-1}$处的值.

组合：

$A(ω^k) = A_{even}(ν^k) + ω^kA_{odd}(ν^k), 0 ≤k < n/2$

$A(ω^{k+n/2}) = A_{even}(ν^k) - ω^kA_{odd}(ν^k), 0 ≤k < n/2$

$ω^{k+n/2}= -ω^k，ν^k = (ω^k)^2 = (ω^{k+n/2})^2$

FFT算法 O(n log n)

fft(n,$a^0,a^1, …, a^{n-1}$) {

​ if(n == 1) return $a_0$

​ $(e_0,e_1,…,e_{n/2-1}) ←FFT(n/2, a_0,a_2,a_4,…,a_{n-2}) $

​ $(d_0,d_1,…,d_{n/2-1}) ←FFT(n/2, a_1,a_3,a_5,…,a_{n-1})$

​ for k = 0 to n/2 -1 {

​ $ω^k←e^{2πik/n}$

​ $y_k←e_k+ ω^kd_k$

​ $y_{k+n/2}←e_k-ω^kd_k$}

​ return ($y_0,y_1,…,y_{n-1}$)

}

傅立叶变换逆变换

$F_n×G_n=I_n$

把 $ω^{-1}=e^{-2πi / n}$看成是n次单位根的生成元.

IFFT算法 O(n log n)

ifft(n,$a^0,a^1, …, a^{n-1}$) {

​ if(n == 1) return $a_0$

​ $(e_0,e_1,…,e_{n/2-1}) ←FFT(n/2, a_0,a_2,a_4,…,a_{n-2}) $

​ $(d_0,d_1,…,d_{n/2-1}) ←FFT(n/2, a_1,a_3,a_5,…,a_{n-1})$

​ for k = 0 to n/2 -1 {

​ $ω^k←e^{-2πik/n}$

​ $y_k←(e_k+ ω^kd_k)/n$

​ $y_{k+n/2}←(e_k-ω^kd_k)/n$}

​ return ($y_0,y_1,…,y_{n-1}$)

}