常见算法思想5：分治法

分治算法采取了各个击破的方法，将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。我们只要求出子问题的解，就可得到原问题的解。

在编程过程中，我们经常遇到处理数据相当多、求解过程比较复杂、直接求解法会比较耗时的问题。在求解这类问题时，我们可以采用“各个击破”的方法。具体做法是先把这个问题分解成几个较小的子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个大问题的解法。如果这些子问题还是比较大，还可以继续再把它们分成几个更小的小子问题，依此类推，直至可以直接求出解为止。这就是分治策略的基本思想。

使用分治算法解题的一般步骤如下所示： （1）分解，将要解决的问题划分成若干个规模较小的同类问题。 （2）求解，当子问题划分得足够小时，用较简单的方法解决。 （3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

（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的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)
	}
}