五大常用算法 - 分治法

分治法

1. 分治概念

分治，即分而治之。将比较复杂的问题分解成多个相同、或者相似的子问题，再将子问题分解成更多的子问题，直到问题的规模可以简单的直接求解。将子问题的解合并即为原问题的解。

例如，对于一个问题规模为n的原问题，如果该问题可以很容易求解，则直接求解。否则可以拆分为k(1<k<=n)个规模较小的子问题，这些子问题相互独立并且与原问题相同或相似。通过递归，反复使用分治法，可以将子问题分解为更小规模的K’(1<k’<=k)个子问题，直到可以简单求解。合并子问题解得到原问题解。

tips: 分治和递归通常是相辅相成，同时使用的。
tips: 分治法的算法复杂性随着问题规模n的增大而增大。
tips: 当递归消耗大的时候，可以考虑使用迭代。递归更像是自顶向下解决问题，迭代是自底向上解决问题。迭代的效率比递归高，不需要重复计算。

2. 分治法步骤

(1) 分治法中，每一层递归都包含三个步骤

分解(Divide): 将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。

解决(Conquer): 递归地求解子问题。如果子问题的规模足够小，则停止递归，直接求解。

合并(Combine): 将子问题的解组合成原问题的解

(2) 算法通用实现

Divide-and-Conquer(P)
if (P<n0) // P是为题的规模，n0是问题可直接解出的阀值
	return ADHOC(P) // ADHOC是分治法中的基本子算法。当P,n0时，可直接用ADHOC(P)求解
else
	将P分解成较小子问题P1,P2...Pk
	for i: from 1 to k
		solution i = Divide-and-Conquer(Pi) //递归解决每个子问题
	Solution = Merge(solution 1..i) //合并子问题的解
	return Solution

tips: 找阀值n0+ADHOC()—–>递归因子+递归函数

3. 分治法适用条件

分治法应用的条件：

(1) 问题的规模缩小到一定程度，就能简单的直接求解

(2)问题可以拆分为规模较小的相同子问题（最优子结构性）

(3)子问题的解可以通过合并，得到原问题的解

(4)原问题分解得到的子问题是相互独立的，子问题之间没有重叠（相同子子问题）

如果(3)不能满足，则可以考虑使用贪心算法（局部最优解->整体最优解)，或者使用动态规划。
如果(4)不能满足，则可以使用动态规划，分治依然可以使用，但是需要重复递归，算法消耗大效率低。

4. 常见问题

《剑指 offer》相关问题