【算法】分治

封面画师：Nengoro(ネんごろぅ)     封面ID：66613178

本文参考视频：小马哥教育(SEEMYGO) 2019年 恋上数据结构与算法（第二季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

1. 分治

1.1 基本含义

分治，英文 Divide And Conquer，意为分开并战胜，即分而治之、分治。

分治的一般步骤是：

1. 将原问题分解成若干个规模较小的子问题（子问题和原问题的结构一样，只是规模不一样）；
2. 子问题又不断分解成规模更小的子问题，直到不能再分解（直到可以轻易计算出子问题的解）；
3. 利用子问题的解推导出原问题的解。

因此分治策略非常适合用递归。

注意： 子问题之间是相互独立的。

分治的应用：

• 快速排序
• 归并排序
• Karatsuba 算法（大数乘法）

1.2 Master Theorem

Master Theorem，即主定理。

分治通常遵守一种通用模式。解决规模为 n 的问题，分解成 a 个规模为 $\frac{n}{b}$ 的子问题，然后在 $O(n^d)$ 时间内将子问题的解合并起来。

算法运行时间为：$T(n) = aT(\frac{n}{b}) + O(n^d), \quad a \gt 0, \quad b \gt 1, \quad d \ge 0$。

针对以上公式有：

• $d \gt log_ba, \quad T(n) = O(n^d)$
• $d = log_ba, \quad T(n) = O(n^dlog_n)$
• $d \lt log_ba, \quad T(n) = O(n^{log_ba})$

比如归并排序的运行时间是：$T(n) = 2T(\frac{n}{2}) + O(n)$，套用分治的运算时间公式有 $a = 2, b = 2, d = 1$，所以 $T(n) = O(nlogn)$。

2. 分治的练习

2.1 最大连续子序列和

来源 LeetCode 第 53 题：最大子数组和

给定一个长度为 n 的整数序列，求它的最大连续子序列和。比如 –2、1、–3、4、–1、2、1、–5、4 的最大连续子序列和是 $4 + (–1) + 2 + 1 = 6$。

这道题也属于最大切片问题（最大区段，Greatest Slice）。

概念拓展：子串、子数组、子区间必须是连续的，子序列是可以不连续的。

暴力出奇迹

穷举出所有可能的连续子序列，并计算出它们的和，最后取它们中的最大值。

思路解释：提供两个指针 A、B，最开始时 A 和 B 都指向数组中的第一个元素，之后 A 保持不动，B 每次以步长 1 向数组末尾移动，每次移动时计算由 A 到 B 之间组成的子序列之和，保存最大的和，直到 B 指向数组末位元素。然后 A 向后移动一位，B 也指向相同的位置，重复先前的操作，每次求得的子序列和都和保存的最大的和进行比较，不断更新最大的值，直到 A 和 B 都指向数组的末位。

不难写出以下代码：

/**
 * @author mofan
 * @date 2022/11/12 19:52
 */
public class SubArray {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(nums));
    }

    static int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        for (int begin = 0; begin < nums.length; begin++) {
            for (int end = begin; end < nums.length; end++) {
                // sum 是 begin 到 end 之间子序列的和
                int sum = 0;
                for (int i = begin; i < end; i++) {
                    sum += nums[i];
                }
                max = Math.max(max, sum);
            }
        }
        return max;
    }
}

不难看出这段代码的时间复杂度是 $O(n^3)$。

尽管是暴力求解，但也还有可以优化的地方。上方代码在每次求取 begin 到 end 之间的子序列和时都进行了重复运算，完全不需要每次都从头遍历求和，因为本次的子序列之和就是上次子序列之和加上当前 end 指向的元素。

static int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int max = Integer.MIN_VALUE;
    for (int begin = 0; begin < nums.length; begin++) {
        int sum = 0;
        for (int end = begin; end < nums.length; end++) {
            sum += nums[end];
            max = Math.max(max, sum);
        }
    }
    return max;
}

优化后的时间复杂度是 $O(n^2)$。

分治法

将序列均匀地分割成 2 个子序列：

$[begin, end) = [begin, mid) + [mid, end), \quad mid = (begin + end) \gt\gt 1$

假设问题的解是 $S[i, j)$，那么问题的解有三种可能：

• $[i, j)$ 存在于 $[begin, mid)$ 中
• $[i, j)$ 存在于 $[mid, end)$ 中
• $[i, j)$ 一部分存在于 $[begin, mid)$ 中，另一部分存在于 $[mid, end)$ 中，那么有：
  • $[i, j) = [i, mid) + [mid, j)$
  • $[i, mid) = max\{S[k, mid)\},\quad begin \le k \lt mid$

也就是说，以 mid 为分割线，求出左边最大的子序列和、求出右边最大的子序列和、求出横跨左右两边的最大子序列和，在这三个子序列和中选取最大的就是此题的解。

public static void main(String[] args) {
    int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    System.out.println(maxSubArray(nums, 0, nums.length));
}

static int maxSubArray(int[] nums, int begin, int end) {
    if (end - begin < 2) {
        return nums[begin];
    }
    int mid = (begin + end) >>> 1;

    int leftMax = nums[mid - 1];
    int leftSum = 0;
    for (int i = mid - 1; i >= begin; i--) {
        leftSum += nums[i];
        leftMax = Math.max(leftMax, leftSum);
    }

    int rightMax = nums[mid];
    int rightSum = 0;
    for (int i = mid; i < end; i++) {
        rightSum += nums[i];
        rightMax = Math.max(rightMax, rightSum);
    }

    return Math.max(
        leftMax + rightMax,
        Math.max(
            maxSubArray(nums, begin, mid),
            maxSubArray(nums, mid, end)
        )
    );
}

上述代码的时间复杂度即为解的三种可能的时间复杂度之和：

• 求出左边最大的子序列和的时间复杂度是：$T(\frac{n}{2})$
• 求出右边最大的子序列和的时间复杂度是：$T(\frac{n}{2})$
• 求出横跨左右两边的最大子序列和的时间复杂度是：$T(n)$

这些很好理解，求出左右两边的子序列的时间复杂度是折半的，因此都为 $T(\frac{n}{2})$，在求横跨左右两边的最大子序列和时，使用循环进行了元素的扫描，因此时间复杂度为 $O(n)$。

代码整体的时间复杂度是：$T(n)=2T(\frac{n}{2})+O(n)$，这与归并排序的时间复杂度是一样的，因此 $T(n) = O(nlogn)$。

2.2 大数乘法

本节只讲理论，不讲实现！

2 个超大的数（比如 2 个 100 位的数），如何进行乘法而不会数据溢出呢？

按照学习的乘法运算，在进行 n 位数之间的相乘时，大约需要进行 $n^2$ 次个位数的相乘。

比如计算 $36 \times 54$：

一共进行了 4 次个位数的相乘，并且时间复杂度是 $O(n^2)$。

时间复杂度是怎么计算的呢？

根据图示可知，将 n 位数与 n 位数的相乘可以看成 $\frac{n}{2} + \frac{n}{2}$ 位数与 $\frac{n}{2} + \frac{n}{2}$ 位数的相乘，每次计算都将其位数拆分为原来的一半，因此不难得出这个过程的时间复杂度是 $4T(\frac{n}{2})$，这还没完，还需要把计算的结果相加，一共需要加 n 次，因此相加的时间复杂度是 $O(n)$。

最终得到的时间复杂度是 $T(n)=4T(\frac{n}{2})+O(n)$，根据先前给出的主定理不难得出整体的时间复杂度为 $O(n^2)$。

Karatsuba 算法

1960 年 Anatolii Alexeevitch Karatsuba 提出了 Karatsuba 算法，提高了大数乘法的效率。

他发现 $BC + AD = AC + BD - (A - B)(C - D)$，然后可以修改先前的计算方式，减少乘法计算的次数（按照下图可以理解为将 4 次乘法的计算提升为 3 次乘法的计算）：

那修改后的时间复杂度是多少？

$AC$ 与 $BD$ 的时间复杂度都是 $T(\frac{n}{2})$，这在先前已经说过了，那 $(A - B)(C - D)$ 的时间复杂度呢？

最坏情况下，$A - B$ 结果的位数还是 $A$ 位，$C - D$ 结果的位数也还是 $C$ 位，因此 $(A - B)(C - D)$ 的时间复杂度与 $AC$、$BD$ 的时间复杂度是一样的，仍为 $T(\frac{n}{2})$，最后仍别忘了还需要把这些值加起来。

因此可得时间复杂度为 $T(n)=3T(\frac{n}{2})+O(n)$，根据主定理可知时间复杂度 $T(n)=O(n^{log_23})$，约为 $O(n^{1.585})$，相比于先前的 $O(n^2)$ 得到了提升。