分治策略的基本思想
分治策略（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)
Read full article from 分治策略 | Algorithm
No comments:
Post a Comment