分治法

????问题的分解肯定不是一步到位，往往需要反复使用分治手段，在多个层次上层层分解，这种分解的方法很自然地导致了递归方式的使用。

T DivideAndConquer(P)
{
    if(P 可以直接解决)
    {
        T <- P 的结果;
        return T;
    }

    将 P 分解为子问题{P1, P2,..., Pn};
    for_each(Pi : {P1, P2,..., Pn})
    {
        ti <- DivideAndConquer(Pi); //递归解决子问题 Pi
    }
    T <- Merge(t1, t2,...,tn); //合并子问题的解

    return T;
}

分治法的三步骤

1. 分解????：将问题分解为若干个规模较小，相互独立且与原问题形式相同的子问题，确保各个子问题的解具有相同的子结构。
2. 解决????：如果上一步分解得到的子问题可以解决，则解决这些子问题，否则，对每个子问题使用和上一步相同的方法再次分解，然后求解分解后的子问题，这个过程可能是一个递归的过程。
3. 合并❤️：将上一步解决的各个子问题的解通过某种规则合并起来，得到原问题的解。

用武之地????

????在数学上，只要能用数学归纳法证明的问题，一般也都可以应用分治法解决，这也是一个应用分治法的强烈信号。

• 最轻、最重问题（在一堆形状相同的物品中找出最重或最轻的那一个）
• 矩阵乘法
• 大整数乘法以及排序（例如，快速排序和归并排序）
• 快速傅立叶变换算法
• Karatsuba 乘法算法
• 二分查找
• 棋盘覆盖问题

总结

分治法的难点是如何将子问题分解，并且将子问题的解合并出原始问题的解，针对不同的问题，通常有不同的分解与合并方式。
快速排序算法：选择一个标兵数，根据标兵数将序列分成两个子序列，最后将两个已经排序的子序列一前一后拼接在标兵数前后
快速傅立叶变换：将一个 N 点离散傅立叶变换，按照奇偶关系分成两个 N/2 点离散傅立叶变换，其合并思想就是将两个 N/2 点离散傅立叶变换结果按照蝶形运算的位置关系重新排列成一个 N 点序列
Karatsuba 大整数乘法算法：分解思想是将两个参与计算的 n 位大数各自分成两部分：a + b 和 c + d，其中，a 和 c 分别是这两个大整数的整数幂部分，b 和 d 分别是它们的剩余部分，然后利用乘法的分解公式：(a + b)(c + d) = ac + ad + bc + bd，将其分解为四次小规模大数的乘法计算，并且利用一个小技巧将其化解成三次乘法和少量移位操作。最终结果的合并思想就是用几次加法对小规模乘法的结果进行求和，得到原始问题的解

分解的艺术（持续更新）

对字符串类问题分解子问题，通常考虑的方法有两个

❗️用字符串的开始位置和字符串的长度表示一个子字符串，对于一个长度为 n 的字符串，用这种方法定义的子问题就是“从位置 i 开始，长度为 m 的字符串，原始问题就是从位置 1 开始，长度为 n 的字符串。
❗️❗️用字符串的位置区间来表示一个子字符串，同样对于一个长度为 n 的字符串，用这种方法定义的子问题就是“从位置 i 开始，到位置 j 结束的字符串，原始问题就是从位置 1 开始到位置 n 结束的字符串。

合并的艺术（持续更新）

代码实现

1、快速排序

public void quickSort(int[] array, int low, int high){
    if(array == null){
        return;
    }
    int i = low;
    int j = high;
    int key = a[low];
    
    if(low < high){
        while(low < high){
            while(i < j && key <= a[j]){
                j--;
            }
            a[i] = a[j];
            while(i < j && key >= a[i]){
                i++;
            }
            a[j] = a[i];
            a[i] = key;
        }
        quickSort(array, low, i-1);
        quickSort(array, i+1, high);
    }
}

2、快速傅里叶变换算法

public class DFT {
 
	public Complex[] dft(Complex[] x) {
		int n = x.length;
		// exp(-2i*n*PI)=cos(-2*n*PI)+i*sin(-2*n*PI)=1
		if (n == 1)
			return x;
		Complex[] result = new Complex[n];
		for (int i = 0; i < n; i++) {
			result[i] = new Complex(0, 0);
			for (int k = 0; k < n; k++) {
				//使用欧拉公式e^(-i*2pi*k/N) = cos(-2pi*k/N) + i*sin(-2pi*k/N)
				double p = -2 * k * Math.PI / n;
				Complex m = new Complex(Math.cos(p), Math.sin(p));
				result[i].plus(x[k].multiple(m));
			}
		}
		return result;
	}
}