分治算法

递归：算法一次或多次递归地调用其自身已解决紧密相关的若干子问题。这些算法遵循分治法的思想。

分治算法三个步骤：

分解：原问题拆分成若干个子问题，这些子问题是原问题的规模较小的实例

解决：递归地求解各个子问题。若子问题的规模足够小，则直接求解。

合并：这些子问题的解成为原问题的解

分析分治算法

使用递归方程来描述运行时间，T(n)是规模为n的一个问题的运行时间。c代表足够小的规模，可以直接解决问题。

将原问题拆分为a个子问题，每个子问题解决原问题的1/b，

D(n)为分解问题成子问题需要的时间，C(n)为合并子问题的解为原问题解需要的时间。

若n<=c, T(n) = Θ(1)

其他情况，T(n) = aT(n/b) + D(n) + C(n)