分治算法是一个通过以下步骤解决大型问题的策略

1. 将问题分解成更小的子问题
2. 求解子问题
3. 合并子问题并得到最终解

为了使用分治算法，会用到递归。了解不同语言中的递归：

• Java中的递归
• Python中的递归
• C++中的递归

分治算法是怎么运作的？

以下是相关步骤：

1. 分：使用递归把给定问题分为子问题
2. 治：用递归的方式解决较小的子问题。如果子问题足够小，直接求解
3. 合并：将作为递归过程一部分的子问题的解进行合并，从而解决实际问题。

通过一个例子来理解一下

下面，我们将使用分治法（也就是归并排序）对一个数组进行排序。

1. 给定一个数组如下：

2. 分：把数组分成2半

继续递归的将每个子部分分成2半，直到分成1个元素

3. 合并单个元素为一个有序的数组，这里，治和合并是同步进行的

时间复杂度

分治算法的时间复杂度通过主定理计算

备注

我这里就不翻译计算过程了，时间复杂度是: O(n log n)

分治 VS 动态规划

分治法将一个问题分解为若干较小的子问题；这些子问题会通过递归的方式进一步求解。每个子问题的结果不会被存储起来供日后使用。然而，在动态规划方法中，每个子问题的结果都会被存储起来，以便之后参考。

当同一个子问题不会被多次求解时，使用分治法。当一个子问题的结果在未来需要被多次使用时，使用动态规划方法。

通过一个例子来理解一下。假设我们求一个斐波那契数列。那么，

分治法

fib(n)
   If n < 2, return 1
   Else , return f(n - 1) + f(n - 2)

动态规划

mem = []
fib(n)
    If n in mem: return mem[n]
    else,
      If n < 2, f = 1
      else , f = f(n - 1) + f(n - 2)
      mem[n] = f
      return f

在动态规划中，mem存储了每一个子问题的结果

分治算法的优点

• 使用朴素方法进行两个矩阵相乘的时间复杂度是$O(n^3)$，而使用分治法（即施特拉森矩阵乘法）的时间复杂度是$O(n^2.8074)$。分治还简化了其他问题，比如汉诺塔问题。
• 分治适合多进程系统
• 高效的利用了内存缓存

分治法的应用

• 二分查找
• 归并排序
• 快速排序
• 施特拉森矩阵乘法
• 卡拉苏巴算法