分治法

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)$。（这一点有个扩展版本：若 $f(n)=\mathrm{\Theta }(n^{{\log }_{b}a}{\log }^{k}n)$ 对某个常数 $k\ge 0$ 成立，则 $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}{\log }^{k+1}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)$$

   3. 引理 1 的证明： 设 $n=b^k$ 对于某个非负整数 $k$ 成立。这意味着 $k={\log }_{b}n$。 通过迭代展开来求解 $T(n)$。

      • 第 0 层 (初始调用): $T(n)=aT(n/b)+f(n)$

      • 第 1 层 (展开 $T(n/b)$):

        $T(n)=a[aT\left(\frac{n}{b^2}\right)+f\left(\frac{n}{b}\right)]+f(n)$

        $T(n)=a^{2}T\left(\frac{n}{b^2}\right)+af\left(\frac{n}{b}\right)+f(n)$

      • 第 2 层 (展开 $T(n/b^2)$):

        $T(n)=a^2[aT\left(\frac{n}{b^3}\right)+f\left(\frac{n}{b^2}\right)]+af\left(\frac{n}{b}\right)+f(n)$

        $T(n)=a^{3}T\left(\frac{n}{b^3}\right)+a^{2}f\left(\frac{n}{b^2}\right)+af\left(\frac{n}{b}\right)+f(n)$

      观察这个模式，在第 $j$ 次迭代（或者说在递归树的第 $j$ 层，根为第 0 层）之后，我们可以得到：

      $$T(n)=a^{j}T\left(\frac{n}{b^j}\right)+\sum _{i=0}^{j-1}{a}^{i}f\left(\frac{n}{b^i}\right)$$

      (注意求和的上限是 $j-1$，因为 $f(n)=a^{0}f(n/b^0)$ 是第 0 项)

      递归会持续进行，直到子问题的规模达到 1，即当 $\frac{n}{b^j}=1$ 时。

      因为 $n=b^k$，所以 $\frac{b^k}{b^j}=1⟹b^{k-j}=1⟹k-j=0⟹j=k$。

      所以，递归的深度是 $k={\log }_{b}n$。

      当 $j=k={\log }_{b}n$ 时，我们代入上面的通用公式：

      $$T(n)=a^{{\log }_{b}n}T\left(\frac{n}{b^{{\log }_{b}n}}\right)+\sum _{j=0}^{{\log }_{b}n-1}{a}^{j}f\left(\frac{n}{b^j}\right)$$

      现在我们来处理这两个部分。

   4. 第一部分（递归终止项）： $a^{{\log }_{b}n}T\left(\frac{n}{b^{{\log }_{b}n}}\right)$

      我们知道 $b^{{\log }_{b}n}=n$ (对数的定义)，所以，$\frac{n}{b^{{\log }_{b}n}}=\frac{n}{n}=1$。

      因此，这一项变为 $a^{{\log }_{b}n}T(1)$。

      根据对数换底公式的一个性质 $x^{{\log }_{y}z}=z^{{\log }_{y}x}$，我们有 $a^{{\log }_{b}n}=n^{{\log }_{b}a}$。

      因为 $T(1)=\mathrm{\Theta }(1)$ (表示 $T(1)$ 是一个常数或者被常数界定)，所以 $a^{{\log }_{b}n}T(1)=n^{{\log }_{b}a}\cdot \mathrm{\Theta }(1)=\mathrm{\Theta }(n^{{\log }_{b}a})$。

   5. 第二部分（各层代价之和）： $\sum _{j=0}^{{\log }_{b}n-1}{a}^{j}f\left(\frac{n}{b^j}\right)$

      这部分保持不变，它代表了递归过程中在每一层（除了最底层的基础情况）合并子问题解或分解问题所产生的代价之和。

      将这两部分结合起来，我们就得到了引理的结果：

      $$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)$$

      至此，引理 1 证明完毕。这个引理是主定理证明的核心步骤：它将递归式 $T(n)$ 分解为了两部分：一部分是所有叶子节点（基础情况）的总代价，另一部分是所有内部节点的总代价（即所有 $f(n/b^j)$ 项的总和）。主定理的三种情况实际上就是比较这两部分哪一个在渐近意义上占主导地位。

   6. 证明主定理的三种情况

      引理 1 告诉我们，对于 $n=b^k$：

      $$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)$$

      我们将这个和式记为 $S(n)=\sum _{j=0}^{{\log }_{b}n-1}{a}^{j}f\left(\frac{n}{b^j}\right)$。

      主定理的三种情况取决于函数 $f(n)$ 相对于 $n^{{\log }_{b}a}$ 的增长速度，这实质上是在比较 $S(n)$ 与 $\mathrm{\Theta }(n^{{\log }_{b}a})$ 的大小。

      • 情况 1: 若 $f(n)=O(n^{{\log }_{b}a-\epsilon })$ 对某个常数 $\epsilon >0$ 成立。

        这意味着存在正常数 $c_1$ 和 $n_0$，使得对于所有 $n\ge n_0$ 且 $n$ 是 $b$ 的幂，$f(n)\le c_1{n}^{{\log }_{b}a-\epsilon }$。 我们需要估计 $S(n)$:

        $$S(n)=\sum _{j=0}^{{\log }_{b}n-1}{a}^{j}f\left(\frac{n}{b^j}\right)$$

        代入 $f(n)$ 的上界：

        $$S(n)\le \sum _{j=0}^{{\log }_{b}n-1}{a}^j{c}_1{\left(\frac{n}{b^j}\right)}^{{\log }_{b}a-\epsilon }$$$$S(n)\le c_1{n}^{{\log }_{b}a-\epsilon }\sum _{j=0}^{{\log }_{b}n-1}{a}^j{\left(\frac{1}{b^j}\right)}^{{\log }_{b}a-\epsilon }$$$$S(n)\le c_1{n}^{{\log }_{b}a-\epsilon }\sum _{j=0}^{{\log }_{b}n-1}{a}^j\frac{1}{(b^{{\log }_{b}a}{)}^j(b^{-\epsilon }{)}^j}$$

        因为 $b^{{\log }_{b}a}=a$，上式变为：

        $$S(n)\le c_1{n}^{{\log }_{b}a-\epsilon }\sum _{j=0}^{{\log }_{b}n-1}{a}^j\frac{1}{a^j(b^{\epsilon }{)}^{-j}}=c_1{n}^{{\log }_{b}a-\epsilon }\sum _{j=0}^{{\log }_{b}n-1}(b^{\epsilon }{)}^j$$

        这是一个等比数列求和，公比 $r=b^{\epsilon }$。因为 $b>1$ 且 $\epsilon >0$，所以 $b^{\epsilon }>1$。

        $$\sum _{j=0}^{{\log }_{b}n-1}(b^{\epsilon }{)}^j=\frac{(b^{\epsilon }{)}^{{\log }_{b}n}-1}{b^{\epsilon }-1}=\frac{(b^{{\log }_{b}n}{)}^{\epsilon }-1}{b^{\epsilon }-1}=\frac{n^{\epsilon }-1}{b^{\epsilon }-1}$$

        因此，

        $$S(n)\le c_1{n}^{{\log }_{b}a-\epsilon }\cdot \frac{n^{\epsilon }-1}{b^{\epsilon }-1}=c_1\frac{n^{{\log }_{b}a}-n^{{\log }_{b}a-\epsilon }}{b^{\epsilon }-1}$$

        因为 $b^{\epsilon }-1$ 是一个正的常数，且 $n^{{\log }_{b}a-\epsilon }$ 是低阶项，所以

        $$S(n)=O(n^{{\log }_{b}a})$$

        将其代回引理 1 的结果：

        $$T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})+O(n^{{\log }_{b}a})$$

        因此，$T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$。
        (更严格地说，因为 $f(n)$ 是非负的，所以 $S(n)\ge 0$。如果 $f(n)=\mathrm{\Omega }(1)$，那么 $S(n)$ 至少是某个小的正项，但其上界是 $O(n^{{\log }_{b}a})$，所以最终由 $\mathrm{\Theta }(n^{{\log }_{b}a})$ 主导。)

      • 情况 2: 若 $f(n)=\mathrm{\Theta }(n^{{\log }_{b}a}{\log }^{k}n)$ 对某个常数 $k\ge 0$ 成立。

        我们先考虑 $k=0$ 的情况： $f(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$。

        这意味着存在正常数 $c_1,c_2$ 和 $n_0$，使得 $c_1{n}^{{\log }_{b}a}\le f(n)\le c_2{n}^{{\log }_{b}a}$ 对 $n\ge n_0$。

        $$S(n)=\sum _{j=0}^{{\log }_{b}n-1}{a}^{j}f\left(\frac{n}{b^j}\right)$$

        代入 $f(n)$ 的 $\mathrm{\Theta }$ 界：

        $$S(n)=\sum _{j=0}^{{\log }_{b}n-1}{a}^j\mathrm{\Theta }\left({\left(\frac{n}{b^j}\right)}^{{\log }_{b}a}\right)$$$$S(n)=\sum _{j=0}^{{\log }_{b}n-1}{a}^j\mathrm{\Theta }\left(\frac{n^{{\log }_{b}a}}{(b^{{\log }_{b}a}{)}^j}\right)=\sum _{j=0}^{{\log }_{b}n-1}{a}^j\mathrm{\Theta }\left(\frac{n^{{\log }_{b}a}}{a^j}\right)$$$$S(n)=\sum _{j=0}^{{\log }_{b}n-1}\mathrm{\Theta }(n^{{\log }_{b}a})$$

        这个和式中有 ${\log }_{b}n$ 项，每一项都是 $\mathrm{\Theta }(n^{{\log }_{b}a})$。

        因此，$S(n)=\mathrm{\Theta }(n^{{\log }_{b}a}{\log }_{b}n)=\mathrm{\Theta }(n^{{\log }_{b}a}\log n)$。

        将其代回引理 1 的结果：

        $$T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})+\mathrm{\Theta }(n^{{\log }_{b}a}\log n)$$

        因此，$T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\log n)$。

        如果 $k\ge 0$:

        $$S(n)=\sum _{j=0}^{{\log }_{b}n-1}{a}^j\mathrm{\Theta }({\left(\frac{n}{b^j}\right)}^{{\log }_{b}a}{\log }^k\left(\frac{n}{b^j}\right))$$$$S(n)=\sum _{j=0}^{{\log }_{b}n-1}\mathrm{\Theta }(n^{{\log }_{b}a}{\log }^k\left(\frac{n}{b^j}\right))$$

        $\log (n/b^j)=\log n-j\log b$。当 $j$ 接近 ${\log }_{b}n$ 时，这一项接近 0。当 $j$ 较小时，这一项接近 $\log n$。

        下面证明这个和式的结果是 $\mathrm{\Theta }(n^{{\log }_{b}a}{\log }^{k+1}n)$：

        为简化符号，设 $L={\log }_{b}n$。因为 $n=b^L$，则 $n/b^j=b^{L-j}$。

        则 $\log (n/b^j)=\log (b^{L-j})=(L-j)\log b$。

        因此，和式中的项可以写为 $\mathrm{\Theta }(n^{{\log }_{b}a}((L-j)\log b{)}^k)$.

        因为 $\log b$ 是一个常数，我们可以将其吸收到 $\mathrm{\Theta }$ 符号中：

        $$S(n)=\sum _{j=0}^{L-1}\mathrm{\Theta }(n^{{\log }_{b}a}(L-j{)}^k)$$

        我们可以将 $n^{{\log }_{b}a}$ 因子提出来：

        $$S(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\sum _{j=0}^{L-1}(L-j{)}^k)$$

        现在，我们需要计算和式 $H(L)=\sum _{j=0}^{L-1}(L-j{)}^k$，这是一个关于 $L-j$ 的 $k$ 次幂的和。

        令 $m=L-j$。当 $j=0$, $m=L$。当 $j=L-1$, $m=1$。

        所以，和式可以改写为：

        $$H(L)=\sum _{m=1}^L{m}^k$$

        我们知道：

        $$\sum _{m=1}^L{m}^k\approx {\int }_1^L{x}^{k}dx={\left[\frac{x^{k+1}}{k+1}\right]}_1^L=\frac{L^{k+1}}{k+1}-\frac{1}{k+1}=\mathrm{\Theta }(L^{k+1})$$

        因此，$\sum _{m=1}^L{m}^k=\mathrm{\Theta }(L^{k+1})$

        因为 $L={\log }_{b}n$，所以 $H(L)=\mathrm{\Theta }(({\log }_{b}n{)}^{k+1})$.

        因为 ${\log }_{b}n=\frac{\log n}{\log b}$，所以 $({\log }_{b}n{)}^{k+1}=\mathrm{\Theta }((\log n{)}^{k+1})$。

        因此，

        $$\sum _{j=0}^{L-1}(L-j{)}^k=\mathrm{\Theta }({\log }^{k+1}n)$$

        将这个结果代回 $S(n)$ 的表达式：

        $$S(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\cdot \mathrm{\Theta }({\log }^{k+1}n))=\mathrm{\Theta }(n^{{\log }_{b}a}{\log }^{k+1}n)$$

        所以 $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})+\mathrm{\Theta }(n^{{\log }_{b}a}{\log }^{k+1}n)=\mathrm{\Theta }(n^{{\log }_{b}a}{\log }^{k+1}n)$。

      • 情况 3: 若 $f(n)=\mathrm{\Omega }(n^{{\log }_{b}a+\epsilon })$ 对某个常数 $\epsilon >0$ 成立，并且若 $af(n/b)\le cf(n)$ 对某个常数 $c<1$ 和所有足够大的 $n$ (正则性条件) 成立。

        正则性条件 $af(n/b)\le cf(n)$ 可以被迭代应用：

        $$a^{j}f(n/b^j)\le c{a}^{j-1}f(n/b^{j-1})\le c^2{a}^{j-2}f(n/b^{j-2})\le \cdots \le c^{j}f(n)$$

        现在看和式 $S(n)$:

        $$S(n)=\sum _{j=0}^{{\log }_{b}n-1}{a}^{j}f\left(\frac{n}{b^j}\right)$$

        因为 $f(n)$ 是非负的，我们只关注上界。

        $$S(n)=f(n)+af(n/b)+a^{2}f(n/b^2)+\cdots +a^{{\log }_{b}n-1}f(n/b^{{\log }_{b}n-1})$$

        我们知道 $a^{j}f(n/b^j)\le c^{j}f(n)$。

        所以，$S(n)=\sum _{j=0}^{{\log }_{b}n-1}{a}^{j}f\left(\frac{n}{b^j}\right)$.

        我们需要证明这个和式由 $f(n)$ (即 $j=0$ 的项) 主导。

        $S(n)=a^{0}f(n/b^0)+a^{1}f(n/b^1)+\cdots =f(n)+af(n/b)+a^{2}f(n/b^2)+\dots$

        我们从后往前看。设 $m_j=n/b^j$. 则 $af(m_{j+1})\le cf(m_j)$。

        $S(n)=f(n)+af(n/b)+\dots$

        因为 $af(n/b)\le cf(n)$，所以 $a^{2}f(n/b^2)=a\cdot (af((n/b)/b))\le a\cdot cf(n/b)\le c(af(n/b))\le c\cdot (cf(n))=c^{2}f(n)$.

        一般地，$a^{j}f(n/b^j)\le c^{j}f(n)$。

        所以

        $$S(n)=\sum _{j=0}^{{\log }_{b}n-1}{a}^{j}f\left(\frac{n}{b^j}\right)\le \sum _{j=0}^{{\log }_{b}n-1}{c}^{j}f(n)=f(n)\sum _{j=0}^{{\log }_{b}n-1}{c}^j$$

        因为 $0\le c<1$，这是一个收敛的几何级数（即使项数趋于无穷也收敛）。

        $$\sum _{j=0}^{{\log }_{b}n-1}{c}^j<\sum _{j=0}^{\mathrm{\infty }}{c}^j=\frac{1}{1-c}=\mathrm{const}$$

        因此，$S(n)\le f(n)\cdot \frac{1}{1-c}=O(f(n))$。

        因为 $f(n)$ 本身就是和式中的第一项（当 $j=0$ 时，$a^{0}f(n/b^0)=f(n)$），且所有项非负，所以 $S(n)=\mathrm{\Omega }(f(n))$。

        因此，$S(n)=\mathrm{\Theta }(f(n))$。

        将其代回引理 1 的结果：

        $$T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})+\mathrm{\Theta }(f(n))$$

        在情况 3 中，条件 $f(n)=\mathrm{\Omega }(n^{{\log }_{b}a+\epsilon })$ 意味着 $f(n)$ 的增长速度快于 $n^{{\log }_{b}a}$。

        因此，$n^{{\log }_{b}a}=o(f(n))$。

        因此，$T(n)=\mathrm{\Theta }(f(n))$。

   证毕。

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}$$

其中：

1. $x\ge 1$ 是一个实数，
2. $x_0$ 是一个常数，使得对于 $1\le i\le k$，$x_0\ge 1/b_i$ 且 $x_0\ge 1/(1-b_i)$,
3. 对于 $1\le i\le k$，$a_i>0$ 是一个常数,
4. 对于 $1\le i\le k$，$b_i\in (0,1)$ 是一个常数,
5. $k\ge 1$ 是一个常数，且
6. $g(x)$ 是一个满足下面指定的多项式增长条件的非负函数。

多项式增长条件

定义： 如果存在正常数 $c_1,c_2$，使得对于所有 $x>1$，所有 $1\le i\le k$，以及所有 $u\in [b_{i}x,x]$，$c_{1}g(x)\le g(u)\le c_{2}g(x)$， 则称 $g(x)$ 满足多项式增长条件。

注： 如果 $|g^{\prime }(x)|$ 在 $x$ 中以多项式为上界，则 $g(x)$ 满足多项式增长条件。例如，对于任何常数 $\alpha ,\beta \in \mathbb{R}$，$g(x)=x^{\alpha }{\log }^{\beta }x$ 满足多项式增长条件。

总能找到唯一实数 $p$，使得 $\sum _{i=1}^k{a}_i{b}_i^p=1$。

递归式的解为：

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

例子：

• 若 $T(x)=2T(x/4)+3T(x/6)+\mathrm{\Theta }(x\log x)$，则 $p=1$ 且 $T(x)=\mathrm{\Theta }(x{\log }^{2}x)$。
• 若 $T(x)=2T(x/2)+\frac{3}{2}T(3x/4)+\mathrm{\Theta }(x^2/\log x)$，则 $p=2$ 且 $T(x)=\mathrm{\Theta }(x^2/\log \log x)$。
• 若 $T(x)=T(x/2)+\mathrm{\Theta }(\log x)$，则 $p=0$ 且 $T(x)=\mathrm{\Theta }({\log }^{2}x)$。
• 若 $T(x)=\frac{1}{2}T(x/2)+\mathrm{\Theta }(1/x)$，则 $p=-1$ 且 $T(x)=\mathrm{\Theta }((\log x)/x)$。
• 若 $T(x)=4T(x/2)+\mathrm{\Theta }(x)$，则 $p=2$ 且 $T(x)=\mathrm{\Theta }(x^2)$。

4.5.2 使用 Akra-Bazzi 方法

4.5.3 证明 Akra-Bazzi 方法

放一个简单的归纳证明，参考 Tom Leighton 的 Notes on Better Master Theorems for Divide-and-Conquer Recurrences。

$$T(x)=\{\begin{array}{ll}\mathrm{\Theta }(1)& \text{若 }1\le x\le x_0\\ \sum _{i=1}^k{a}_{i}T(b_{i}x)+g(x)& \text{若 }x>x_0\end{array}(1)$$

定理 1： 给定一个由方程 (1) 指定形式的递归式，令 $p$ 为满足 $\sum _{i=1}^k{a}_i{b}_i^p=1$ 的唯一实数，则

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

定理 1 的证明利用了以下来自微积分的简单引理。

引理 1： 如果 $g(x)$ 是一个满足多项式增长条件的非负函数，则存在正常数 $c_3,c_4$，使得对于 $1\le i\le k$ 且所有 $x\ge 1$，

$$c_{3}g(x)\le x^p{\int }_{b_{i}x}^x\frac{g(u)}{u^{p+1}}\mathrm{d}u\le c_{4}g(x)$$

证明： 从多项式增长条件可得：

$$x^p{\int }_{b_{i}x}^x\frac{g(u)}{u^{p+1}}\mathrm{d}u\le x^p(x-b_{i}x)\frac{c_{2}g(x)}{min\{(b_{i}x{)}^{p+1},x^{p+1}\}}=\frac{(1-b_i)c_2}{min\{1,b_i^{p+1}\}}g(x)\le c_{4}g(x)$$

其中定义 $c_4$ 为满足以下条件的常数：

$$c_4\ge \frac{(1-b_i)c_2}{min\{1,b_i^{p+1}\}}$$

其中 $1\le i\le k$。

类似地，

$$x^p{\int }_{b_{i}x}^x\frac{g(u)}{u^{p+1}}\mathrm{d}u\ge x^p(x-b_{i}x)\frac{c_{1}g(x)}{max\{(b_{i}x{)}^{p+1},x^{p+1}\}}=\frac{(1-b_i)c_1}{max\{1,b_i^{p+1}\}}g(x)\ge c_{3}g(x)$$

其中我们定义 $c_3$ 为满足以下条件的常数：

$$c_3\ge \frac{(1-b_i)c_1}{max\{1,b_i^{p+1}\}}$$

其中 $1\le i\le k$。

使用归纳法来证明定理 1：将 $x$ 的定义域划分为区间 $I_0=[1,x_0]$ 和 $I_j=(x_0+j-1,x_0+j]$ （对于 $j\ge 1$）。

根据 $x_0$ 的定义，我们知道如果 $x\in I_j$ 对于某个 $j\ge 1$，则对于 $1\le i\le k$，$b_{i}x\in I_{j^{\prime }}$ 对于某个 $j^{\prime }<j$。这是因为 $b_{i}x>b_i(x_0+j-1)\ge b_i{x}_0\ge 1$，并且因为 $b_{i}x\le b_i(x_0+j)\le x_0+j-(1-b_i)x_0\le x_0+j-1$。因此，我们知道在 $[1,x_0]$ 之后的任何区间中 $T$ 的值仅取决于 $T$ 在先前区间中的值。

定理 1 的证明： 首先证明存在一个正常数 $c_5$，使得对于所有 $x>x_0$，

$$T(x)\ge c_5{x}^p(1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u)$$

对包含 $x$ 的区间 $I_j$ 进行归纳。当 $j=0$ 时，基本情况成立，因为当 $x\in [1,x_0]$ 时，$T(x)=\mathrm{\Theta }(1)$（前提是我们选择足够小的 $c_5$）。

归纳步骤的论证如下：

$$\begin{array}{rl}T(x)& =\sum _{i=1}^k{a}_{i}T(b_{i}x)+g(x)\\ & \ge \sum _{i=1}^k{a}_i{c}_5(b_{i}x{)}^p(1+{\int }_1^{b_{i}x}\frac{g(u)}{u^{p+1}}\mathrm{d}u)+g(x)\text{(根据归纳假设)}\\ & =c_5{x}^p\sum _{i=1}^k{a}_i{b}_i^p(1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u-{\int }_{b_{i}x}^x\frac{g(u)}{u^{p+1}}du)+g(x)\\ & \ge c_5{x}^p((1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u)\sum _{i=1}^k{a}_i{b}_i^p-\sum _{i=1}^k{a}_i{b}_i^p{\int }_{b_{i}x}^x\frac{g(u)}{u^{p+1}}\mathrm{d}u)+g(x)\\ & \ge c_5{x}^p((1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u)-\frac{c_4}{x^p}g(x))+g(x)\text{(根据引理1及 }\sum a_i{b}_i^p=1\text{)}\\ & =c_5{x}^p(1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u)+g(x)-c_5{c}_{4}g(x)\\ & \ge c_5{x}^p(1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u)\end{array}$$

前提是 $c_5\le 1/c_4$。

还需证明上界，即存在一个正常数 $c_6$ 使得对于所有 $x>x_0$，

$$T(x)\le c_6{x}^p(1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u)$$

上界与下界的证明几乎完全相同，不再完整复述。我们只需要确保 $c_6$ 选择得足够大，以便满足基本情况，并且 $c_6\ge 1/c_3$。因此，我们可以得出结论：

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

注： 如果 $g(x)$ 的增长速度快于 $x$ 的任何多项式，则 $T(x)=\mathrm{\Theta }(g(x))$。因此，如果 $g(x)$ 不满足多项式增长条件，则定理 1 不一定成立。

变种：

虽然上面分析的递归式类别相当广泛，但在实践中出现的递归式通常与方程 (1) 中指定的类别略有不同。例如，在算法设计中，以下形式的递归式很常见：

$$T(x)\le \sum _{i=1}^k{a}_{i}T(\lfloor b_{i}x\rfloor )+g(x)$$

一般来说，在递归式中包含取整函数（floor 和 ceiling）并不会显著改变解的性质，但证明这一事实的过程往往相当繁琐且具有特殊性。接下来，我们将会描述一类通用的变种（包括取整函数），并表明该类中的变种不影响递归式的解（除了常数项）。特别地，定理 1 的解对于以下形式的所有递归式都成立：

$$T(x)=\{\begin{array}{ll}\mathrm{\Theta }(1)& \text{若 }1\le x\le x_0\\ \sum _{i=1}^k{a}_{i}T(b_{i}x+h_i(x))+g(x)& \text{若 }x>x_0\end{array}(2)$$

其中

1. $x,x_0,a_i,b_i,k,$ 和 $g(x)$ 都满足上面指定的条件，
2. 存在某个常数 $ϵ>0$，使得当 $x\ge x_0$ 时，对于 $1\le i\le k$，$|h_i(x)|\le x/({\log }^{1+ϵ}x)$,
3. 存在正常数 $c_1$ 和 $c_2$，使得对于所有 $x\ge 1$，所有 $1\le i\le k$，以及所有 $u\in [b_{i}x+h_i(x),x]$， $c_{1}g(x)\le g(u)\le c_{2}g(x)$, 且
4. $x_0$ 为足够大的常数，使得对于任何 $i\le k$ 和任何 $x\ge x_0$， (a) ${(1-\frac{1}{b_i{\log }^{1+ϵ}x})}^p(1+\frac{1}{{\log }^{ϵ/2}(b_{i}x+x/{\log }^{1+ϵ}x)})\ge 1+\frac{1}{{\log }^{ϵ/2}x}$ (b) ${(1+\frac{1}{b_i{\log }^{1+ϵ}x})}^p(1-\frac{1}{{\log }^{ϵ/2}(b_{i}x+x/{\log }^{1+ϵ}x)})\le 1-\frac{1}{{\log }^{ϵ/2}x}$ (c) $\frac{1}{2}(1+\frac{1}{{\log }^{ϵ/2}x})\le 1$ (d) $2(1-\frac{1}{{\log }^{ϵ/2}x})\ge 1$.

可以使用标准的泰勒级数展开和渐近分析来证明存在这样一个常数 $x_0$。

例如，可以选择 $h_i(x)$ 使得 $h_i(x)=\lceil b_{i}x\rceil -b_{i}x$，从而将定理 1 扩展到处理向上取整函数。在这种情况下，$|h_i(x)|<1$。也可以使用大得多的函数。例如，对于 $x>1$，可以设置 $h_i(x)=-\sqrt{x}$ 或 $h_i(x)=x/({\log }^{2}x)$。

为了分析更一般的递归式，需要下面这个和引理 1 相似的引理。

引理 2： 存在正常数 $c_3,c_4$，使得对于 $1\le i\le k$ 且所有 $x\ge 1$，

$$c_{3}g(x)\le x^p{\int }_{b_{i}x+h_i(x)}^x\frac{g(u)}{u^{p+1}}\mathrm{d}u\le c_{4}g(x)$$

引理 2 的证明与引理 1 的证明相同，只是使用上面第 3 节的约束 3 来代替第 2 节的多项式增长条件。

定理 2： 给定一个方程 (2) 中指定的形式的递归式，令 $p$ 为满足 $\sum _{i=1}^k{a}_i{b}_i^p=1$ 的唯一实数。则

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

证明： 证明与定理 1 的证明非常相似，主要区别在于使用了一个稍微更强的归纳假设。特别地，首先证明存在一个正常数 $c_5$，使得对于所有 $x>x_0$，

$$T(x)\ge c_5{x}^p(1+\frac{1}{{\log }^{ϵ/2}x})(1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u)$$

通过对包含 $x$ 的区间 $I_j$ 进行归纳。当 $j=0$ 时，基本情况由 $T(x)=\mathrm{\Theta }(1)$ 当 $x\in [1,x_0]$ 时成立（前提是我们选择足够小的 $c_5$）。

归纳步骤的论证如下：

$$\begin{array}{rl}T(x)& =\sum _{i=1}^k{a}_{i}T(b_{i}x+h_i(x))+g(x)\\ & \ge \sum _{i=1}^k{a}_i{c}_5(b_{i}x+h_i(x){)}^p(1+\frac{1}{{\log }^{ϵ/2}(b_{i}x+h_i(x))})(1+{\int }_1^{b_{i}x+h_i(x)}\frac{g(u)}{u^{p+1}}\mathrm{d}u)+g(x)\text{(根据归纳假设)}\\ & \ge \sum _{i=1}^k{a}_i{b}_i^p{c}_5{x}^p{(1-\frac{1}{b_i{\log }^{1+ϵ}x})}^p(1+\frac{1}{{\log }^{ϵ/2}(b_{i}x+x/{\log }^{1+ϵ}x)})\times (1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u-{\int }_{b_{i}x+h_i(x)}^x\frac{g(u)}{u^{p+1}}\mathrm{d}u)+g(x)\text{(根据 }{h}_i(x)\text{ 的界限)}\\ & \ge \sum _{i=1}^k{a}_i{b}_i^p{c}_5{x}^p(1+\frac{1}{{\log }^{ϵ/2}x})(1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u-\frac{c_4}{x^p}g(x))+g(x)\text{(根据 }{x}_0\text{ 上的约束4(a)和引理2)}\\ & =c_5{x}^p(1+\frac{1}{{\log }^{ϵ/2}x})(1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u-\frac{c_4}{x^p}g(x))\sum _{i=1}^k{a}_i{b}_i^p+g(x)(\text{因为 }\sum a_i{b}_i^p=1)\\ & =c_5{x}^p(1+\frac{1}{{\log }^{ϵ/2}x})(1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u)+g(x)-c_5{c}_4(1+\frac{1}{{\log }^{ϵ/2}x})g(x)\\ & \ge c_5{x}^p(1+\frac{1}{{\log }^{ϵ/2}x})(1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u)\end{array}$$

前提是 $c_5\le 1/(2c_4)$ （根据 $x_0$ 上的约束4(c)）。

上界的证明非常相似。在这种情况下，我们通过归纳证明存在一个正常数 $c_6$，使得对于所有 $x>x_0$，

$$T(x)\le c_6{x}^p(1-\frac{1}{{\log }^{ϵ/2}x})(1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u)$$

基本情况如前所述。归纳步骤的论证如下：

$$\begin{array}{rl}T(x)& =\sum _{i=1}^k{a}_{i}T(b_{i}x+h_i(x))+g(x)\\ & \le \sum _{i=1}^k{a}_i{c}_6(b_{i}x+h_i(x){)}^p(1-\frac{1}{{\log }^{ϵ/2}(b_{i}x+h_i(x))})(1+{\int }_1^{b_{i}x+h_i(x)}\frac{g(u)}{u^{p+1}}\mathrm{d}u)+g(x)\text{(根据归纳假设)}\\ & \le \sum _{i=1}^k{a}_i{b}_i^p{c}_6{x}^p{(1+\frac{1}{b_i{\log }^{1+ϵ}x})}^p(1-\frac{1}{{\log }^{ϵ/2}(b_{i}x+x/{\log }^{1+ϵ}x)})\times (1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u-{\int }_{b_{i}x+h_i(x)}^x\frac{g(u)}{u^{p+1}}\mathrm{d}u)+g(x)\text{(根据 }{h}_i(x)\text{ 的界限)}\\ & \le \sum _{i=1}^k{a}_i{b}_i^p{c}_6{x}^p(1-\frac{1}{{\log }^{ϵ/2}x})(1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u-\frac{c_3}{x^p}g(x))+g(x)\text{(根据 }{x}_0\text{ 上的约束4(b)和引理2)}\\ & =c_6{x}^p(1-\frac{1}{{\log }^{ϵ/2}x})(1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u-\frac{c_3}{x^p}g(x))\sum _{i=1}^k{a}_i{b}_i^p+g(x)(\text{因为 }\sum a_i{b}_i^p=1)\\ & =c_6{x}^p(1-\frac{1}{{\log }^{ϵ/2}x})(1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u)+g(x)-c_3{c}_6(1-\frac{1}{{\log }^{ϵ/2}x})g(x)\\ & \le c_6{x}^p(1-\frac{1}{{\log }^{ϵ/2}x})(1+{\int }_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u)\end{array}$$

前提是 $c_6\ge 2/c_3$ （根据 $x_0$ 上的约束4(d)）。

因此，我们可以得出结论：

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

备注： 值得注意的是，对 $|h_i(x)|$ 大小的 $x/{\log }^{1+ϵ}x$ 限制几乎是紧的，因为以下递归式的解

$$T(x)=\{\begin{array}{ll}\mathrm{\Theta }(1)& \text{若 }1\le x\le x_0\\ 2T(x/2+x/\log x)& \text{若 }x>x_0\end{array}$$

是 $T(x)=x{\log }^{\mathrm{\Theta }(1)}x$，这与没有 $x/\log x$ 项的递归式的解 $\mathrm{\Theta }(x)$ 不同。

5. 常见的分治算法

5.0 归并排序

上面介绍过，不再赘述。

5.1 Karatsuba 大数乘法

Karatsuba 算法是一种用于快速计算两个大整数乘积的算法。它比传统的小学乘法算法（按位相乘再相加）具有更好的渐近时间复杂度。

5.1.1 传统大数乘法算法

假设我们要计算两个 $n$ 位大整数 $X$ 和 $Y$ 的乘积。为了方便分析，我们设 $n$ 是 2 的幂：

我们可以将每个数分成两半，每半大约有 $n/2$ 位：

$$X=A\cdot B^m+C$$$$Y=D\cdot B^m+E$$

其中 $B$ 是基数（例如 $B=10$ 对于十进制数，或 $B=2$ 对于二进制数内部表示），$m\approx n/2$。$A,C,D,E$ 是大约 $n/2$ 位的整数。

那么，$X\cdot Y=(A\cdot B^m+C)(D\cdot B^m+E)=AD\cdot B^{2m}+(AE+CD)\cdot B^m+CE$。

这个过程需要计算 4 个 $n/2$ 位整数的乘积（$AD,AE,CD,CE$），以及若干次加法和移位（乘以 $B^m$ 或 $B^{2m}$ 相当于移位）。

加法和移位操作的时间复杂度是 $O(n)$。

因此，递归式为：

$$T(n)=4T(n/2)+O(n)$$

根据主定理，其中 $a=4,b=2,f(n)=O(n)$，${\log }_{b}a={\log }_{2}4=2$。

由于 $f(n)=O(n)=O(n^{2-\epsilon })$ 其中 $\epsilon =1>0$，属于主定理情况 $1$，所以 $T(n)=\mathrm{\Theta }(n^2)$。

这就是传统算法的时间复杂度。

5.1.2 Karatsuba 算法的描述

Karatsuba 算法的核心思想是通过巧妙的代数变换，将 4 次 $n/2$ 位乘法减少到 3 次，代价是增加一些加减法。

与上面类似，我们将 $X$ 和 $Y$ 分解：

$$X=A\cdot B^m+C$$$$Y=D\cdot B^m+E$$

我们需要计算 $AD$, $CE$, 和 $AE+CD$。

Karatsuba 观察到 $(A+C)(D+E)=AD+AE+CD+CE$，所以，关键的中间项 $AE+CD$ 可以表示为：

$$AE+CD=(A+C)(D+E)-AD-CE$$

这样，我们只需要计算三次 $n/2$ 位（或略大于 $n/2$ 位，因为 $A+C$ 可能比 $A$ 或 $C$ 多一位）的乘法：

1. $P_1=AD$
2. $P_2=CE$
3. $P_3=(A+C)(D+E)$

然后，最终结果是： $X\cdot Y=P_1\cdot B^{2m}+(P_3-P_1-P_2)\cdot B^m+P_2$

算法步骤：

1. 分解： 将 $n$ 位数 $X,Y$ 分解为 $A,C,D,E$，每个约 $n/2$ 位。 $X=A\cdot B^{n/2}+C$$Y=D\cdot B^{n/2}+E$ （这里假设 $n$ 是偶数，如果不是，可以补零或者取 $m=\lfloor n/2\rfloor$）
2. 计算和： 计算 $S_A=A+C$ 和 $S_D=D+E$。这些是 $O(n)$ 的加法。
3. 递归计算乘积：
   • $P_1=\text{Karatsuba}(A,D)$
   • $P_2=\text{Karatsuba}(C,E)$
   • $P_3=\text{Karatsuba}(S_A,S_D)$
4. 组合结果：
   • 计算 $K=P_3-P_1-P_2$ （两次 $O(n)$ 的减法）
   • $X\cdot Y=P_1\cdot B^n+K\cdot B^{n/2}+P_2$ （两次移位和两次 $O(n)$ 的加法）

5.1.3 Karatsuba 算法的时间复杂度

1. 得到递归式： 算法进行了 3 次 $n/2$ 位整数的乘法，以及常数次的 $O(n)$ 的加法、减法和移位操作。

   $$T(n)=\{\begin{array}{ll}\mathrm{\Theta }(1)& \text{if }n=1\text{ (或小于某个阈值)}\\ 3T(n/2)+\mathrm{\Theta }(n)& \text{if }n>1\end{array}$$

2. 使用主定理：（其中 $a=3,b=2$）

   $f(n)=\mathrm{\Theta }(n)$，${\log }_{b}a={\log }_{2}3\approx 1.585$。

   比较 $f(n)$ 与 $n^{{\log }_{b}a}=n^{{\log }_{2}3}$：

   $f(n)=\mathrm{\Theta }(n)=O(n^{{\log }_{2}3-\epsilon })$，其中 $\epsilon ={\log }_{2}3-1\approx 0.585>0$。

   这符合主定理的情况 1，因此，$T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})=\mathrm{\Theta }(n^{{\log }_{2}3})$。

由于 ${\log }_{2}3\approx 1.585<2$，Karatsuba 算法的 $\mathrm{\Theta }(n^{{\log }_{2}3})$ 优于传统算法的 $\mathrm{\Theta }(n^2)$。

5.2 Strassen 矩阵乘法

为了方便起见，我们只考虑方阵，且矩阵边长为 2 的幂。

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\times n$ 的方阵 $A$ 和 $B$，其乘积 $C=AB$ 也是一个 $n\times n$ 的方阵。根据定义，计算 $C$ 中的每一个元素 $c_{ij}$ 需要 $n$ 次乘法和 $n-1$ 次加法：

$$c_{ij}=a_{i1}{b}_{1j}+a_{i2}{b}_{2j}+\cdots +a_{in}{b}_{nj}$$

由于矩阵 $C$ 有 $n^2$ 个元素，所以总共需要的乘法次数是 $n^2\cdot n=n^3$，总共需要的加法次数是 $n^2\cdot (n-1)=n^3-n^2$。

因此，普通矩阵乘法算法的时间复杂度是 $\mathrm{\Theta }(n^3)$。

如果进行普通的分治算法：

如果将 $n\times n$ 矩阵 $A,B,C$ 均分解为 4 个 $\frac{n}{2}\times \frac{n}{2}$ 的子矩阵：

$$A=\left(\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right),B=\left(\begin{array}{cc}{B}_{11}& B_{12}\\ B_{21}& B_{22}\end{array}\right),C=\left(\begin{array}{cc}{C}_{11}& C_{12}\\ C_{21}& C_{22}\end{array}\right)$$

则

$C_{11}=A_{11}{B}_{11}+A_{12}{B}_{21}$
$C_{12}=A_{11}{B}_{12}+A_{12}{B}_{22}$
$C_{21}=A_{21}{B}_{11}+A_{22}{B}_{21}$
$C_{22}=A_{21}{B}_{12}+A_{22}{B}_{22}$

这需要 8 次 $\frac{n}{2}\times \frac{n}{2}$ 规模的矩阵乘法和 4 次 $\frac{n}{2}\times \frac{n}{2}$ 规模的矩阵加法。矩阵加法的时间复杂度是 $\mathrm{\Theta }((n/2{)}^2)=\mathrm{\Theta }(n^2)$，递归式为 $T(n)=8T(n/2)+\mathrm{\Theta }(n^2)$。

根据主定理，$a=8,b=2,f(n)=\mathrm{\Theta }(n^2)$。

${\log }_{b}a={\log }_{2}8=3$。

$f(n)=\mathrm{\Theta }(n^2)=O(n^{3-\epsilon })$ 其中 $\epsilon =1>0$。属于主定理情况 1。

所以，$T(n)=\mathrm{\Theta }(n^3)$，和普通矩阵乘法算法时间复杂度一致。

5.2.3 Strassen 矩阵乘法算法的描述

1. 核心：让递归树的分支减少一个：递归进行 7 次而不是 8 次 $\frac{n}{2}\times \frac{n}{2}$ 矩阵乘法。
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 个 $\frac{n}{2}\times \frac{n}{2}$ 矩阵的乘积 $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_{22}\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. 花费 $\mathrm{\Theta }(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 }_{b}a={\log }_{2}7\approx 2.807$。

   比较 $f(n)$ 与 $n^{{\log }_{b}a}=n^{{\log }_{2}7}$：$f(n)=\mathrm{\Theta }(n^2)$。

   因为 ${\log }_{2}7>2$，所以存在 $\epsilon ={\log }_{2}7-2>0$，使得 $f(n)=\mathrm{\Theta }(n^2)=O(n^{{\log }_{2}7-\epsilon })$，这符合主定理的情况 1。

   因此，$T(n)=\mathrm{\Theta }(n^{{\log }_{2}7})$。

   因为 ${\log }_{2}7\approx 2.807<3$，所以 Strassen 算法的 $\mathrm{\Theta }(n^{{\log }_{2}7})$ 优于普通矩阵乘法的 $\mathrm{\Theta }(n^3)$。

5.3 快速数论变换 (Fast Number Theoretic Transformation, NTT)

快速数论变换 (NTT) 是一种在特定有限域（通常是整数模素数 $p$ 的环 ${\mathbb{Z}}_p$）中进行的离散傅里叶变换 (DFT)。它与快速傅里叶变换 (FFT) 具有非常相似的算法结构，但所有运算都在模 $p$ 意义下进行，从而避免了 FFT 中的浮点数精度问题，并能得到精确的整数结果。NTT 主要用于高效地计算两个大整数（或系数为整数的两个多项式）的卷积。

5.3.1 背景：多项式乘法与卷积

两个多项式 $A(x)=\sum _{i=0}^{m-1}{a}_i{x}^i$ 和 $B(x)=\sum _{i=0}^{k-1}{b}_i{x}^i$ 的乘积 $C(x)=A(x)B(x)=\sum _{j=0}^{m+k-2}{c}_j{x}^j$ 的系数 $c_j$ 可以表示为卷积形式：

$$c_j=\sum _{i=0}^j{a}_i{b}_{j-i}$$

(其中，如果 $i\ge m$，则 $a_i=0$；如果 $j-i\ge k$，则 $b_{j-i}=0$)。

直接计算卷积需要 $O(mk)$ 次运算。如果 $m\approx k\approx N$, 则复杂度为 $O(N^2)$。 利用 DFT (或 NTT)，我们可以将多项式乘法的复杂度降低到 $O(N\log N)$。

其原理是：

1. 点值表示： 将多项式 $A(x)$ 和 $B(x)$ 分别在 $N$ 个选定的点上求值，得到它们点值表示 $(x_s,A(x_s))$ 和 $(x_s,B(x_s))$。$N$ 必须大于等于 $m+k-1$ (结果多项式的次数加1)。
2. 点值乘法： 对于每个点 $x_s$，计算 $C(x_s)=A(x_s)\cdot B(x_s)$。这需要 $O(N)$ 次乘法。
3. 插值： 从 $C(x)$ 的 $N$ 个点值表示 $(x_s,C(x_s))$ 中恢复出系数表示 $C(x)=\sum c_j{x}^j$。

DFT (以及 FFT 作为其快速算法) 使用复数域中的 $N$ 次单位根作为求值点。NTT 则使用有限域中的 $N$ 次“原根” (primitive $N$-th root of unity)。

5.3.2 NTT 的数学基础

1. 有限域/环： NTT 在整数模素数 $p$ 的环 ${\mathbb{Z}}_p=\{0,1,\dots ,p-1\}$ 中进行运算。
2. 原根 (Primitive Root of Unity)： 为了使 NTT 能够顺利进行，我们需要一个元素 $\omega \in {\mathbb{Z}}_p$ 满足：
   • ${\omega }^N\equiv 1(\mathrm{mod}p)$
   • ${\omega }^k\not\equiv 1(\mathrm{mod}p)$ for $1\le k<N$
   • $N$ 是变换的长度，通常取为大于等于结果多项式次数的最小的 2 的幂。 这样的 $\omega$ 称为 ${\mathbb{Z}}_p$ 中的 $N$ 次原根。 为了存在 $N$ 次原根，素数 $p$ 必须满足 $p-1$ 是 $N$ 的倍数 (即 $N|(p-1)$)。这样的素数称为 NTT-friendly prime。例如，对于 $N=2^{20}$，$p=998244353=119\cdot 2^{23}+1$ 是一个常用的 NTT 素数，其一个 $N$ 次原根 (对于合适的 $N$) 可以是 $g^{(p-1)/N}(\mathrm{mod}p)$，其中 $g$ 是 $p$ 的一个原根 (primitive root modulo $p$)，例如 $g=3$ 对于 $p=998244353$。
3. 逆元： 在进行逆变换 (INTT) 时，需要计算 $N^{-1}(\mathrm{mod}p)$。这要求 $N$ 与 $p$ 互素，由于 $p$ 是素数且通常 $N<p$，这个条件一般都满足。

5.3.3 NTT 和 逆NTT (INTT) 的定义

给定一个序列 (多项式系数) $A=(a_0,a_1,\dots ,a_{N-1})$，其 NTT 结果为序列 $\hat{A}=({\hat{a}}_0,{\hat{a}}_1,\dots ,{\hat{a}}_{N-1})$，定义为：

$${\hat{a}}_k=\text{NTT}(A{)}_k=\sum _{j=0}^{N-1}{a}_j{\omega }^{jk}(\mathrm{mod}p)\text{for }k=0,1,\dots ,N-1$$

逆 NTT (INTT) 定义为：

$$a_j=\text{INTT}(\hat{A}{)}_j=N^{-1}\sum _{k=0}^{N-1}{\hat{a}}_k{\omega }^{-jk}(\mathrm{mod}p)\text{for }j=0,1,\dots ,N-1$$

其中 ${\omega }^{-1}$ 是 $\omega$ 在模 $p$ 意义下的逆元。

5.3.4 使用 NTT 计算多项式乘法（卷积）的步骤

设要计算 $A(x)\cdot B(x)=C(x)$。

1. 选择参数：
   • 确定结果多项式 $C(x)$ 的最大可能次数 $d_C=\mathrm{deg}(A)+\mathrm{deg}(B)$。
   • 选择变换长度 $N$，为大于 $d_C$ 的最小的 2 的幂。
   • 选择一个素数 $p$ 使得 $N|(p-1)$，且 $p$ 足够大以容纳 $C(x)$ 的系数（即 $C(x)$ 的任何系数 $c_j$ 的绝对值都小于 $p/2$，如果系数可能为负；或者 $c_j<p$ 如果系数非负）。
   • 找到 ${\mathbb{Z}}_p$ 中的一个 $N$ 次原根 $\omega$。
2. 填充： 将多项式 $A(x)$ 和 $B(x)$ 的系数序列用 0 填充到长度 $N$。
3. 正变换： 计算 $\hat{A}=\text{NTT}(A)$ 和 $\hat{B}=\text{NTT}(B)$。这使用类似 Cooley-Tukey FFT 的分治算法，时间复杂度为 $O(N\log N)$ 次模 $p$ 运算。
4. 点值乘法： 计算点值乘积序列 $\hat{C}$，其中 ${\hat{c}}_k={\hat{a}}_k\cdot {\hat{b}}_k(\mathrm{mod}p)$ for $k=0,\dots ,N-1$。这需要 $O(N)$ 次模 $p$ 乘法。
5. 逆变换： 计算 $C=\text{INTT}(\hat{C})$。这也是 $O(N\log N)$ 次模 $p$ 运算。 序列 $C=(c_0,c_1,\dots ,c_{N-1})$ 的前 $d_C+1$ 个元素就是乘积多项式 $C(x)$ 的系数。

5.3.5 NTT 的时间复杂度

NTT 和 INTT 的分治实现（如 Cooley-Tukey 算法）都具有 $O(N\log N)$ 的时间复杂度，其中 $N$ 是变换长度。每次运算都是模 $p$ 的加法、减法或乘法。 步骤如下：

1. 参数选择和填充：$O(N)$。
2. 两次 NTT：$2\cdot O(N\log N)=O(N\log N)$。
3. 点值乘法：$O(N)$。
4. 一次 INTT：$O(N\log N)$。 因此，使用 NTT 计算两个次数近似为 $N/2$ 的多项式乘法的总时间复杂度是 $\mathrm{\Theta }(N\log N)$。

这比 Karatsuba 算法的 $\mathrm{\Theta }(N^{{\log }_{2}3})$ 对于足够大的 $N$ 更优，并且由于是精确整数运算，在某些领域比 FFT 更受欢迎。

6. 常见的用分治法解决的问题

6.1 最近点对问题

在一个平面上的 $n$ 个点中，找到欧氏距离最小的两个点。

6.2 最大子数组和问题

给定一个整数数组（可正可负），找到一个具有最大和的连续子数组。

此问题有更优解法

对于这个问题来说，分治算法的时间复杂度为 $O(n\log n)$。

然而，存在更优的解法（动态规划或贪心），时间复杂度为 $O(n)$。

6.3 凸包问题

给定平面上 $n$ 个点，找到一个最小的凸多边形，使其包含所有这些点。

此问题有更优解法

对于这个问题来说，分治算法的时间复杂度为 $O(n\log n)$。

然而，存在更优的解法：Jarvis 算法的时间复杂度为 $O(nH)$，当 $H<<n$ 的时候更优；Melkman 算法的时间复杂度为 $O(n)$。

习题

1. 20401 [2.2] 使用主定理，求解以下递归式，并指出运用了主定理的哪种情况。

   • (a) $T(n)=9T(n/3)+n^2$
   • (b) $T(n)=T(2n/3)+\mathrm{\Theta }(1)$
   • (c) $T(n)=3T(n/4)+n\lg n$
   • (d) $T(n)=7T(n/2)+\mathrm{\Theta }(n^2)$
   • (e) $T(n)=2T(n/2)+n^3$
   • (f) $T(n)=4T(n/2)+\mathrm{\Theta }(n^2)$
   • (g) [4.3M] $T(n)=2T(n/2)+n/\lg n$ (思考：这个递归式能直接用主定理的三种基本情况求解吗？为什么？)

2. 对于递归式 $T(n)=T(n-1)+n$，使用代入法证明其解为 $T(n)=O(n^2)$。

3. 对于归并排序的递归式 $T(n)=2T(n/2)+\mathrm{\Theta }(n)$，请：

   • (a) 画出其递归树。
   • (b) 计算出树的每一层的代价总和。
   • (c) 计算树的高度，并求出所有层代价的总和，从而得出 $T(n)$ 的渐近界。

4. 使用换元法，求解递归式 $T(n)=T(\sqrt{n})+\mathrm{\Theta }(\lg \lg n)$ 的时间复杂度。

5. 本教程 6.2 节提到了最大子数组和问题。请设计一个分治算法来解决它。

• (a) 分解：如何将数组分成子问题？
• (b) 解决：子问题的解是什么？
• (c) 合并：这是最关键的一步。一个最大和的子数组可能存在于三个地方：① 完全在左半部分；② 完全在右半部分；③ 跨越了中点。请详细描述如何在线性时间 $\mathrm{\Theta }(n)$ 内找到跨越中点的最大子数组，并结合左右子问题的解，得到原问题的解。
• (d) 写出该分治算法的递归式并求解其时间复杂度。

6. 在一个数组 $A[1\dots n]$ 中，如果存在 $i<j$ 且 $A[i]>A[j]$，则称 $(i,j)$ 是一个逆序对。请设计一个分治算法来计算一个数组中逆序对的总数。

   • 提示：尝试修改归并排序算法。在 merge() 过程中，当右边子数组的元素 R[j] 被复制回原数组时，左边子数组 L 中还剩下多少个元素？这与逆序对有什么关系？
   • 分析你的算法的时间复杂度。

7. 本教程 5.1 节描述的 Karatsuba 算法中，我们把一个大数乘法分解成 3 个规模为 $n/2$ 的乘法。那我们是否可以继续优化，比如把问题分解成 5 个规模为 $n/3$ 的子问题？如果可以，那么时间复杂度会是多少？它会比 Karatsuba 算法更好吗？

8. 在本教程的 merge() 函数实现中，使用了宏 INT_MAX。如果不允许使用这个值，你将如何修改 merge() 函数中的主循环来完成合并操作？