分治算法

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]均为有序，结束