分治算法
1、分治算法设计
Divide:整个问题划分为多个自问题
Conquer:求解各个子问题(递归调用算法)
Combine:合并自问题的解、形成原始问题的解
2、分析递归方程
建立递归方程;求解
3、递归方程建立方法
设输入大小为n,T(n)为时间复杂性
当n<c,T(n) = O(1)
4、时间复杂性分析
Divide阶段的时间复杂度:
划分问题为a个子问题
每个子问题大小为n/b
划分时间可以直接得到=D(n)
Conquer阶段的时间复杂度:
递归调用
Conquer时间=aT(n/b)
Combine阶段的时间复杂度:
时间可以直接得到=C(n)
最后得到递归方程
T(n) = O(1) n ≤ c
T(n) = aT(n/b)+D(n)+C(n) n > c
5、举例:快速排序
Divide:
将数组A[p..r]分为A[p..q]和A[q+1..r]
对于任意x∈[p..q],x ≤ A[q],任意y∈A[q+1..r],y>A[q]
Conquer:
对A[p..q]和A[q+1..r]分别使用快排
Conbine:
A[p..q]和A[q+1..r]均为有序,结束