《算法设计》学习笔记-分治算法
分治算法也是常用的一种解决问题的思路，它把输入分成几个部分，递归地求解每个部分中的问题，然后将这些子问题的解组合成一个整体解。所以，分治算法通常涉及递归关系。
归并排序：把输入分成两个相同大小的部分；通过递归分别解决这两个部分的两个子问题；然后将两个结果组合成一个整体解，只用线性时间进行初始划分和最终重组。证明归并排序的方法的时间复杂度是O(nlogn)。
求解递归的一般方法：一种是展开前几层递归，并确定递归展开时会继续的模式，然后对所有层的运行时间求和；一种是从猜测一个解开始，然后替换到递归关系中，来检查是否有效。
计数逆序：考虑两个排名，如何评估两个排名的差异有多大？我们说两个索引i<j形成逆序，就是a(i)<a(j)，即两个元素顺序不同。计算逆序的个数，数字越大，两个序列差异越大。自然的想法，需要O(n2)的时间。用分治的方法，用分治算法，类似归并排序，可以优化到O(nlogn)。
Merge-and-Count(A,B)
对每个列表维护一个只想它的Current指针，初始化向首个元素
维护一个变量Count记录逆序的个数，初始化为0
While 两个列表都不为空
令ai和bj是Current指针指向的元素
将较小的一个添加到输出列表
If bj是较小的元素 then
让 Count加上A中剩下元素的个数
Endif
将选出较小元素的列表的Current指针向前移
Endwhile
当一个列表为空时，将另一个列表中剩下的元素添加到输出
Return Count和归并的列表寻找最近点对：给定平面中n个点，找到最近的一对点。显而易见，有一个O(n2)的算法，就是逐一计算两个点之间的距离。使用分治的思想，可以优化到O(nlogn)。考虑把点集均匀地分成两个部分，分别计算最近点。合并时考虑两个点被分在两边的情况。
Closet-Pair(P)
构造Px和Py
(p0*,p1*)=Closet-Pair-Rect(Px,Py)
Closet-Pair-Rect(Px,Py)
If |P| <= 3 then
度量所有两个点之间的距离，找到最近点对
Endif
构造Qx,Qy,Px,Py
(q0*,q1*)=Closet-Pair-Rect(Qx,Qy)
(r0*,r1*)=Closet-Pair-Rect(Rx,Ry)
δ=min(d(q0*,q1*),d(r0*,r1*))
x*=集合Q中点最大的x坐标
L={(x,y):x=x*}
S=P与L中相距在a之内的点集
构造Sy
For 每个点s∈Sy，计算从s到Sy中接下来15个点的所有距离
令s,s'是其中距离最小的点对
If d(s,s')< δ then
Return (s,s')
Else if d(q0*,q1*) < d(r0*,r1*)
Return (q0*,q1*)
Else
Return (r0*,r1*)这里可能有个疑问，为什么只计算从s到Sy中接下来15个点的所有距离？具体可以看书上的证明。
整数乘法：用小学生列竖式的算法，时间复杂度为O(n2)。改进的算法基于更巧妙的方式，将乘积分解为部分和。
Recurisve-Multply(x,y)
写x=xi*2n/2+x0
y=yi*2n/2+y0
计算 y1+x0和y1+y0
p=Recurisve-Multply(x1+x0,y1+y0)
x1y1=Recurisve-Multply(x1,y1)
x0y0=Recurisve-Multply(x0,y0)
Return x1y1*2n+(p-x1y1-x0y0)*2n/2+x0y0卷积和快速傅里叶变换：（略）