分治法
分治算法采取了各个击破的方法，将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。我们只要求出子问题的解，就可得到原问题的解。
在编程过程中，我们经常遇到处理数据相当多、求解过程比较复杂、直接求解法会比较耗时的问题。在求解这类问题时，我们可以采用“各个击破”的方法。具体做法是先把这个问题分解成几个较小的子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个大问题的解法。如果这些子问题还是比较大，还可以继续再把它们分成几个更小的小子问题，依此类推，直至可以直接求出解为止。这就是分治策略的基本思想。
使用分治算法解题的一般步骤如下所示：
（1）分解，将要解决的问题划分成若干个规模较小的同类问题。
（2）求解，当子问题划分得足够小时，用较简单的方法解决。
（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
分治法所能解决的问题一般具有以下4个特征。
（1）当问题的规模缩小到一定的程度就可以容易地解决问题。此特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加的。
（2）问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。此特征是应用分治法的前提。它也是大多数问题可以满足的，此特征反映了递归思想的应用。
（3）利用该问题分解出的子问题的解可以合并为该问题的解；此特征最为关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪婪法（贪心法）或动态迭代法。
（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。此特征涉及分治法的效率问题。如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态迭代法更好。
PS：值得注意的是，分治是解编程题常用的一种思想，而大多数分治思想都是用递归法来实现的。
分治算法机理
分治策略的思想起源于对问题解的特性所做出的这样的观察和判断：原问题可以被划分成k个子问题，然后用一种方法将这些子问题的解合并，合并的结果就是原问题的解。既然我们知道可以以某种方式构造出来，就没有必要（使用枚举回溯）进行大批量的搜索了。
枚举、回溯、分治算法利用了计算机工作的第一个特点：高速，不怕数据量大。
分治算法思想利用了计算机工作的第二个特点：重复。
方法实践
典型的分治法应用就是二分查找法，归并排序法等，这两种算法我们在排序算法篇和查找算法篇都讲过，可以去回顾一下,这里还有其他应用：
大数相乘：
步骤简介
Karatsuba算法主要应用于两个大数的相乘，原理是将大数分成两段后变成较小的数位，然后做3次乘法，并附带少量的加法操作和移位操作。
现有两个大数，x，y。
首先将x，y分别拆开成为两部分，可得x1，x0，y1，y0。他们的关系如下：
x = x1 * 10<sup>m</sup> + x0；
y = y1 * 10<sup>m</sup> + y0。其中m为正整数，m < n，且x0，y0 小于 10<sup>m</sup>。
那么 xy = (x1 * 10<sup>m</sup> + x0)(y1 * 10<sup>m</sup> + y0)
=z2 * 10<sup>2m</sup> + z1 * 10<sup>m</sup> + z0，其中：
z2 = x1 * y1；
z1 = x1 * y0 + x0 * y1；
z0 = x0 * y0。
此步骤共需4次乘法，但是由Karatsuba改进以后仅需要3次乘法。因为：
z1 = x1 * y0+ x0 * y1
z1 = (x1 + x0) * (y1 + y0) - x1 * y1 - x0 * y0，
故z1 便可以由一次乘法及加减法得到。
实例展示
设x = 12345，y=6789，令m=3。那么有：
12345 = 12 * 1000 + 345；
6789 = 6 * 1000 + 789。
下面计算：
z2 = 12 * 6 = 72；
z0 = 345 * 789 = 272205；
z1 = (12 + 345) * (6 + 789) - z2 - z0 = 11538。
然后我们按照移位公式（xy = z2 * 10^(2m) + z1 * 10^(m) + z0）可得：
xy = 72 * 1000<sup>2</sup> + 11538 * 1000 + 272205 = 83810205。
Go语言描述
Go的math/big包使用的大数相乘算法就是Karatsuba算法，有兴趣的可看看标准包源码：
// Fast version of z[0:n+n>>1].add(z[0:n+n>>1], x[0:n]) w/o bounds checks.
// Factored out for readability - do not use outside karatsuba.
func karatsubaAdd(z, x nat, n int) {
if c := addVV(z[0:n], z, x); c != 0 {
addVW(z[n:n+n>>1], z[n:], c)
}
}
// Like karatsubaAdd, but does subtract.
func karatsubaSub(z, x nat, n int) {
if c := subVV(z[0:n], z, x); c != 0 {
subVW(z[n:n+n>>1], z[n:], c)
}
}
// Operands that are shorter than karatsubaThreshold are multiplied using
// "grade school" multiplication; for longer operands the Karatsuba algorithm
// is used.
var karatsubaThreshold = 40 // computed by calibrate_test.go
// karatsuba multiplies x and y and leaves the result in z.
// Both x and y must have the same length n and n must be a
// power of 2. The result vector z must have len(z) >= 6*n.
// The (non-normalized) result is placed in z[0 : 2*n].
func karatsuba(z, x, y nat) {
n := len(y)
// Switch to basic multiplication if numbers are odd or small.
// (n is always even if karatsubaThreshold is even, but be
// conservative)
if n&1 != 0 || n < karatsubaThreshold || n < 2 {
basicMul(z, x, y)
return
}
// n&1 == 0 && n >= karatsubaThreshold && n >= 2
// Karatsuba multiplication is based on the observation that
// for two numbers x and y with:
//
// x = x1*b + x0
// y = y1*b + y0
//
// the product x*y can be obtained with 3 products z2, z1, z0
// instead of 4:
//
// x*y = x1*y1*b*b + (x1*y0 + x0*y1)*b + x0*y0
// = z2*b*b + z1*b + z0
//
// with:
//
// xd = x1 - x0
// yd = y0 - y1
//
// z1 = xd*yd + z2 + z0
// = (x1-x0)*(y0 - y1) + z2 + z0
// = x1*y0 - x1*y1 - x0*y0 + x0*y1 + z2 + z0
// = x1*y0 - z2 - z0 + x0*y1 + z2 + z0
// = x1*y0 + x0*y1
// split x, y into "digits"
n2 := n >> 1 // n2 >= 1
x1, x0 := x[n2:], x[0:n2] // x = x1*b + y0
y1, y0 := y[n2:], y[0:n2] // y = y1*b + y0
// z is used for the result and temporary storage:
//
// 6*n 5*n 4*n 3*n 2*n 1*n 0*n
// z = [z2 copy|z0 copy| xd*yd | yd:xd | x1*y1 | x0*y0 ]
//
// For each recursive call of karatsuba, an unused slice of
// z is passed in that has (at least) half the length of the
// caller's z.
// compute z0 and z2 with the result "in place" in z
karatsuba(z, x0, y0) // z0 = x0*y0
karatsuba(z[n:], x1, y1) // z2 = x1*y1
// compute xd (or the negative value if underflow occurs)
s := 1 // sign of product xd*yd
xd := z[2*n : 2*n+n2]
if subVV(xd, x1, x0) != 0 { // x1-x0
s = -s
subVV(xd, x0, x1) // x0-x1
}
// compute yd (or the negative value if underflow occurs)
yd := z[2*n+n2 : 3*n]
if subVV(yd, y0, y1) != 0 { // y0-y1
s = -s
subVV(yd, y1, y0) // y1-y0
}
// p = (x1-x0)*(y0-y1) == x1*y0 - x1*y1 - x0*y0 + x0*y1 for s > 0
// p = (x0-x1)*(y0-y1) == x0*y0 - x0*y1 - x1*y0 + x1*y1 for s < 0
p := z[n*3:]
karatsuba(p, xd, yd)
// save original z2:z0
// (ok to use upper half of z since we're done recursing)
r := z[n*4:]
copy(r, z[:n*2])
// add up all partial products
//
// 2*n n 0
// z = [ z2 | z0 ]
// + [ z0 ]
// + [ z2 ]
// + [ p ]
//
karatsubaAdd(z[n2:], r, n)
karatsubaAdd(z[n2:], r[n:], n)
if s > 0 {
karatsubaAdd(z[n2:], p, n)
} else {
karatsubaSub(z[n2:], p, n)
}
}
