分治策略

分治策略的基本思想

分治策略（Divide and Conquer） 将原始问题划分或者归结为规模较小的子问题 递归或迭代求解每个子问题 将子问题的解综合得到原问题的解

注意： 子问题与原始问题性质完全一样 子问题之间可彼此独立地求解 递归停止时子问题可直接求解（子问题足够小）

二分检索

设计思想 通过x与中位数的比较，将原问题归结为规模减半的子问题 对子问题进行二分检索 当子问题规模为1时，直接比较x与T[m]，若相等则返回m，否则返回0

时间复杂度分析

二分归并排序

设计思想 划分将原问题归结为规模为n/2的2个子问题 继续划分，当子问题规模为1时，划分结束 从规模1到n/2，陆续归并被排好的两个数组，每归并一次，数组规模扩大一倍，直到原始数组

Hanoi塔的递归算法

设计思想 将原问题归结为规模为n-1的2个子问题 继续规约，当子问题规模为1时，归约过程截止 从规模1到n-1，陆续组合两个子问题的解，直到规模为n

小结

将原问题归约为规模小的子问题，子问题与原问题具有相同的性质 子问题规模足够小时可直接求解 算法可以递归也可以迭代实现 算法的分析方法：递推方程

分治算法的一般描述和分析方法

Divide-and-Conquer(P)
if |P| <= c then S(P)
divide P into P1, P2, ...,Pk（划分）
for i<--1 to k
    yi <--Divide-and-Conquer(Pi)（求解子问题）
Return Merge(y1, y2, ..., yk)（综合解）

设计要点

原问题可以划分或者归约为规模较小的子问题 子问题与原问题具有相同的性质 子问题的求解彼此独立 划分时子问题的规模尽可能均衡 子问题规模足够小时可直接求解 子问题的解综合得到原问题的解 算法实现：递归或迭代 两类递推方程 迭代法、递归树 迭代法、换元法、递归树、主定理

芯片测试

输入：

n片芯片，其中好芯片至少比坏芯片多1片

问题：

设计一种测试方法，通过测试从n片芯片中挑出1片好芯片

要求：使用最少的测试次数

快速排序

最坏情况

最好情况

幂乘算法及应用

Fibonacci O(logn)

Fn+1 Fn 1 1 ^n

Fn Fn-1 1 0

改进分治算法的途径1：减少子问题数

利用子问题的依赖关系，使某些子问题的解通过组合其他子问题的解而得到 整数位乘问题

矩阵相乘问题，Strassen矩阵乘法

Coppersmith-Winograd：O(n2.376)

小结

适用于：子问题个数多，划分和综合工作量不太大

改进分治算法的途径2：增加预处理

平面点对问题

输入：平面点集P中有n个点，n>1

输出：P中的两个点，其距离最小

W(n) = aW(n/b) + f(n)