分治法

1. 定义

为了解决一个问题，可以将原问题分解成几个规模较小但类似与原问题的子问题，然后递归地求解子问题，最后将子问题的解合并成原问题的解。

分治模式在每层递归时有三个步骤：

1. 分解：将原问题分解为若干子问题，这些子问题是原问题的规模较小的实例。
2. 解决：递归地求解子问题。
3. 合并：将子问题的解合并成原问题的解。

当子问题足够大，需要递归求解时，称为 递归情况，当子问题足够小，不需要递归求解时，递归已经 触底，称为 基本情况。

2. 示例：归并排序

归并排序 算法遵循上述的分治模式。它的三个步骤可以表述如下：

1. 分解：将乱序的 $n$ 个元素的数组划分为两个长度为 $\frac{n}{2}$ 的子数组。
2. 解决：使用归并排序递归地排序这两个子数组。
3. 合并：将两个已经排好序的数组合并成一个排好序的大数组。

递归触底：当每个子数组长度为 1 时，这个数组已经排好序 😃。这时不再需要继续分解数组。

归并排序的关键操作是 合并 这步，想法很简单：

1. 看两个数组的第一个元素，比较大小，如果数组 A 的第一个元素小于 B 的第一个元素，就把 A 的第一个元素抽出来，反之就把 B 的第一个元素抽出来；
2. 重复第一步，直到有一个数组空了，就把另一个数组剩下的元素直接并到大数组结尾就好。
3. 实际操作中，判断数组是否空这步有一个好方法：
   1. 在 A B 数组的最后各塞一个无穷大的数，重复第一步
   2. 当真的有一个数组空的时候，就不需要采取别的操作，因为 B 数组的任何数都比无穷大小，因此总能把未空的数组的所有元素全部合并

代码实现：

1. 实现 merge_sort() 函数

   1. 传入一个数组，以及要排序的元素的起始下标和终止下标
   2. 如果起始下标等于终止下标，则 递归触底，直接返回；
   3. 否则，把这个区间分成两半（注意两半不能有交叉），分别对这两半进行归并排序，最后调用 merge() 函数进行合并

   void merge_sort(int A[], int p, int r)
   {
       if (p < r) {
           int mid = (p + r) / 2;
           merge_sort(A, p, mid);
           merge_sort(A, mid + 1, r);
           merge(A, p, mid, r);
       }
   }

2. 实现 merge() 函数

   1. 开辟新数组，把数组元素复制一份到新数组，以便稍后移动回原来的数组；

      1. 确定数组大小： 第一个数组存储从 p 到 mid 的元素，第二个数组存储从 mid + 1 到 r 的元素
         定义两个对象 n1 和 n2，分别表示第一个数组和第二个数组的元素个数

         const int n1 = mid - p + 1;
         const int n2 = r - mid;

      2. 开辟数组：使用 malloc() 函数 由于末尾要放一个无穷大的数，所以要多开一个位置

         int* L = malloc((n1 + 1) * sizeof(int));
         int* R = malloc((n2 + 1) * sizeof(int));

      3. 复制元素到新数组

         for (int i = 0; i < n1; i++) {
             L[i] = A[p + i];
         }
         L[n1] = INT_MAX;
         for (int i = 0; i < n2; i++) {
             R[i] = A[(mid + 1) + i];
         }
         R[n2] = INT_MAX;

   2. 依次比较大小，把较小的元素放入原数组； 由于一共只有从 r 到 p 这些数，定义一个对象 k 从 r 循环到 p，把大数放到原数组中

      int i = 0, j = 0;
      for (int k = p; k <= r; k++) {
          if (L[i] <= R[j]) {
              A[k] = L[i];
              i += 1;
          } else {
              A[k] = R[j];
              j += 1;
          }
      }

   3. 释放内存

      free(L);
      free(R);

   merge() 函数全部代码：

   void merge(int A[], const int p, const int mid, const int r)
   {
       const int n1 = mid - p + 1;
       const int n2 = r - mid;
       int* L = malloc((n1 + 1) * sizeof(int));
       int* R = malloc((n2 + 1) * sizeof(int));
       for (int i = 0; i < n1; i++) {
           L[i] = A[p + i];
       }
       L[n1] = INT_MAX;
       for (int i = 0; i < n2; i++) {
           R[i] = A[(mid + 1) + i];
       }
       R[n2] = INT_MAX;
       int i = 0, j = 0;
       for (k = p; k <= r; k++) {
           if (L[i] <= R[j]) {
               A[k] = L[i];
               i += 1;
           } else {
               A[k] = R[j];
               j += 1;
           }
       }
       free(L);
       free(R);
   }

3. 测试代码

   int N[10] = { 13, 5, 9, 6, 11, 2, 4, 7, 1, 8 };
   
   int main(void)
   {
       merge_sort(N, 0, 9);
       for (int i = 0; i < 10; i++) {
           printf("%d ", N[i]);
       }
       return 0;
   }

4. 用递归式分析分治算法

4.1 递归式

递归式，顾名思义就是用一个递归的式子描述算法的运行时间。
以前面的 分治算法 为例：

1. 对于数组长度为 1 的 基本情况，我们不做任何操作
2. 对于长度为 2 的 递归情况，我们把它分解成两个规模为 $\frac{n}{2}$ 的子问题，再加一步 $\mathrm{\Theta }(n)$ 的合并操作。
3. 即：$$T(n)=\{\begin{array}{ll}\mathrm{\Theta }(1)& n=1\\ 2T(n/2)+\mathrm{\Theta }(n)& n>1\end{array}$$用 主定理 可方便求得此递归式的结果是 $\mathrm{\Theta }(n\lg n)$。我们将在 4.4 讲述主定理。

4.2 代入法

代入法 求解分为两步：

1. 猜测解的形式
2. 用 数学归纳法 求出解中的常数，并验证解的正确性

示例：对于递归式 $T(n)=2T\lfloor \frac{n}{2}\rfloor +n$ :

1. 猜测解的形式：$T(n)=O(n\lg n)$
2. 用数学归纳法证明该式子，即证明对于足够大的常数 $c$，有 $T(n)\le cn\lg n$：
   1. 假设对 $\lfloor \frac{n}{2}\rfloor$ 成立： 代入，得$$\begin{array}{rl}T(n)& \le 2(c\lfloor \frac{n}{2}\rfloor \lg \lfloor \frac{n}{2}\rfloor )+n\\ & \le cn\lg \left(\frac{n}{2}\right)+n\\ & =cn\lg n-cn\lg 2+n\\ & =cn\lg n-cn+n\\ & \le cn\lg n\end{array}$$对于任何 $c\ge 1$ 成立。 得到：若对于 $\lfloor n/2\rfloor$ 成立，则对于 $n$ 成立。
   2. 证明对于 $n=2$ 和 $n=3$ 成立： 当 $n=2$ 时，$T(2)=2T(1)+2=4$，此时可以找到一个足够大的 $c$（比如取 2），使 $T(2)\le 2c\lg 2$ 成立。 同理可证 $n=3$ 成立。
   3. 由上面两步，因为在正整数 $n$ 只有等于 2 或 3 时，$\lfloor \frac{n}{2}\rfloor$ 才等于 1，所以我们证明了（为什么？）$T(n)=2T\lfloor n/2\rfloor +n$ 的上界是 $O(n\lg n)$。

有时复杂的递归式可以通过 换元法 化简。

示例：$T(n)=2T(\sqrt{n})+\lg n$ ：

1. 令 $m=\lg n$，则有 $T(2^m)=2T(2^{m/2})+m$；
2. 令 $S(m)=T(2^m)$，则有 $S(m)=2S(m/2)+m$；
3. 根据上面的示例，可得 $S(m)=O(m\lg m)$；
4. 代回原式，得 $T(n)=T(2^m)=S(m)=O(m\lg m)=O(\lg n\lg \lg n)$。

4.3 递归树

4.4 主方法和主定理

4.4.1 概念

主方法 是用 主定理 来解某种递归式的通用的方法，分为三种情况。
它适合求解以下形式的递归式：

$$T(n)=aT\left(\frac{n}{b}\right)+f(n)$$

这个递归式描绘了一种算法的运行时间：每个子问题规模相同；$f(n)$ 是分解和合并的运行时间。

4.4.2 主定理

令 $a\ge 1$ 和 $b>1$ 是常数，$f(n)$ 是一个函数，$T(n)$ 是一个递归式：

$$T(n)=aT\left(\frac{n}{b}\right)+f(n)$$

其中 $\frac{n}{b}$ 可以看作 $\lfloor \frac{n}{b}\rfloor$ 或 $\lceil \frac{n}{b}\rceil$ ，不影响渐进性质。

1. 若 $\mathrm{\exists }ϵ>0$，$f(n)=O\left(n^{{\log }_{b}a-ϵ}\right)$，则 $T(n)=\mathrm{\Theta }\left(n^{{\log }_{b}a}\right)$。
2. 若 $f(n)=\mathrm{\Theta }\left(n^{{\log }_{b}a}\right)$，则 $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\lg n)$。
3. 若 $\mathrm{\exists }ϵ>0$，$f(n)=\mathrm{\Omega }\left(n^{{\log }_{b}a+ϵ}\right)$ ，且 $\mathrm{\exists }c<1,\mathrm{\exists }{n}_0\in {\mathbb{N}}^{\mathbb{\ast }},\mathrm{\forall }n>n_0,af\left(\frac{n}{b}\right)<cf(n)$ ，则 $T(n)=\mathrm{\Theta }(f(n))$

4.4.3 使用主定理

4.4.4 证明主定理

1. 对 b 的幂证明
   1. 为什么是 b 的幂？
      如果 n 是 b 的幂，那么在递归的任意一层中， $\frac{n}{b}$（在结果大于 1 时）都是 正整数。
      在第二点中会对 $\frac{n}{b}$ 可能不是正整数的情况进行证明。
   2. 引理 1：
      若 $a\ge 1$，$b>1$，$f(n)$ 是定义在 b 的幂上的非负函数，$T(n)$ 是定义在 b 的幂上的递归式：$$T(n)=\{\begin{array}{ll}\mathrm{\Theta }(1)& n=1\\ aT\left(\frac{n}{b}\right)+f(n)& n=b^i\end{array}$$其中 i 是正整数。那么：$$T(n)=\mathrm{\Theta }\left(n^{{\log }_{b}a}\right)+\sum _{j=0}^{{\log }_{b}n-1}{a}^{j}f\left(\frac{n}{b^j}\right)$$
2. 对所有正整数证明：向上取整和向下取整

4.5 Akra-Bazzi 方法

4.5.1 简介

Akra-Bazzi 方法 求解以下形式的递归式：

$$T(n)=\{\begin{array}{ll}\mathrm{\Theta }(1)& 1\le n\le n_0\\ \sum _{i=1}^k{a}_{i}T(b_{i}n)+f(n)& n>n_0\end{array}$$

递归式的解为：

$$T(n)=\mathrm{\Theta }\left(n^p(1+{\int }_1^n\frac{f(u)}{u^{p+1}}\mathrm{d}u)\right)$$

4.5.2 使用 Akra-Bazzi 方法

4.5.3 证明 Akra-Bazzi 方法

4.5.4 Tri- Merge Sort

5. 常见的分治算法

5.1 Karatsuba 大数乘法

5.2 Strassen 矩阵乘法

为了方便起见，我们只考虑方阵，且矩阵边长为 2 的幂。 能想出来这种东西的人一定是个天才！ --mdr

5.2.1 矩阵乘法

给定两个矩阵 $A$ 和 $B$，其中 $A=(a_{ik})$ 是 $m\times n$ 的矩阵，$B=(b_{kj})$ 是 $n\times p$ 的矩阵，那么它们的积 $C=AB$ 是 $m\times p$ 的矩阵 $C=(c_{ij})$。其中，对于 $i=1,2,...,m$，对于 $j=1,2,...,p$，有

$$c_{ij}=\sum _{k=1}^n{a}_{ik}{b}_{kj}$$

5.2.2 普通的矩阵乘法算法及时间复杂度

我们需要计算 $n^2$ 个元素，其中每个元素都是 $n$ 个数的和。

5.2.3 Strassen 矩阵乘法算法的描述

1. 核心：让递归树的分支减少一个：递归进行 7 次而不是 8 次
2. 步骤：
   1. 把每个输入矩阵分解为 4 个 $\frac{n}{2}\times \frac{n}{2}$ 的子矩阵：$A_{11},A_{12},A_{21},A_{22},B_{11},B_{12},B_{21},B_{22}$；
   2. 创建 10 个 $\frac{n}{2}\times \frac{n}{2}$ 的矩阵 $S_i$，其中 $i=1,2,3,4,5,6,7,8,9,10$，每个矩阵保存步骤 1 中创建的矩阵的和或差。
   3. 通过步骤 1 和 2 创建的 18 个矩阵，计算出 7 个矩阵的积 $P_i$，其中 $i=1,2,3,4,5,6,7$；
   4. 将 $P_1,P_2,P_3,P_4,P_5,P_6,P_7$ 中的不同组合相加或相减，得到结果矩阵的四个部分 $C_{11},C_{12},C_{21},C_{22}$。
   5. 将上述四个矩阵拼接成一个 $n\times n$ 的矩阵 $C$。
3. 详细过程：
   1. 步骤 2： $S_1=B_{12}-B_{22}$
      $S_2=A_{11}+A_{12}$
      $S_3=A_{21}+A_{22}$
      $S_4=B_{21}-B_{11}$
      $S_5=A_{11}+A_{22}$
      $S_6=B_{11}+B_{22}$
      $S_7=A_{12}-A_{22}$
      $S_8=B_{21}+B_{22}$
      $S_9=A_{11}-A_{21}$
      $S_{10}=B_{11}+B_{12}$
   2. 步骤 3： $P_1=A_{11}\cdot S_1$
      $P_2=S_2\cdot B_{22}$
      $P_3=S_3\cdot B_{11}$
      $P_4=A_{12}\cdot S_4$
      $P_5=S_5\cdot S_6$
      $P_6=S_7\cdot S_8$
      $P_7=S_9\cdot S_{10}$
   3. 步骤 4： $C_{11}=P_5+P_4-P_2+P_6$
      $C_{12}=P_1+P_2$
      $C_{21}=P_3+P_4$
      $C_{22}=P_1+P_5-P_3-P_7$
4. 可以看到，我们用了 7 次 $\frac{n}{2}\times \frac{n}{2}$ 的矩阵乘法 和 18 次 $\frac{n}{2}\times \frac{n}{2}$ 的矩阵加法，完成了 $n\times n$ 的矩阵乘法！😃（将一次乘法优化成 18 次加法 😦）

5.2.4 Strassen 矩阵乘法算法的时间复杂度

1. 得到递归式：
   1. 步骤 1. 2. 4. 均花费 $\mathrm{\Theta }(n^2)$ 时间，步骤 3. 进行 7 次 $\frac{n}{2}\times \frac{n}{2}$ 的矩阵乘法，得到如下递归式：$$T(n)=\{\begin{array}{ll}\mathrm{\Theta }(1)& n=1\\ 7T(n/2)+\mathrm{\Theta }(n^2)& n>1\end{array}$$
2. 使用主定理（其中 $a=7$，$b=2$） 观察主定理的第一种情况，我们发现： ${\log }_{2}7>2$
   $⟹\mathrm{\exists }ϵ>0,{\log }_{2}7-ϵ>2$
   $⟹\mathrm{\exists }ϵ>0,f(n)=\mathrm{\Theta }(n^2)=O(n^{{\log }_{2}7-ϵ})$
   $⟹T(n)=\mathrm{\Theta }(n^{\lg 7})$
   显而易见比平常的 $\mathrm{\Theta }(n^3)$ 的算法时间复杂度低。

5.3 快速数论变换 (Fast Number Theory Transformation, FNTT)