数据结构与算法-进阶（十九）分治

大家好，欢迎来到IT知识分享网。

摘要

分治就是将原问题不断拆分成规模小的问题，直到小问题可以得出答案为止，然后再往上推导出原问题的答案。拆分的问题必须要和原问题结构是一致，这和递归的解答思路较大程度上是一致的。

分治，可以理解为分而治之，核心逻辑就是将原问题分解成若干个小问题，原问题和小问题在结构上是一致的，唯一的区别就是规模不同。然后再将小问题分解出更小的问题，直到无法再分解为止，也就是可以直接或者简单的计算得出问题的答案。最后利用小问题推导出原问题的解。

这个和递归的思想类似，所以分治策略非常适合使用递归来处理，需要特别注意的是，分治策略中的子问题都是相互独立的。

可以应用到分治策略的有快速排序、归并排序和大数乘法等。

递归思想的拆解问题和求解

递归的思想就是将规模大的问题，拆分成规模较小的同类问题，然后将规模较小的问题再拆分成规模更小的同类问题，直到可以直接得出问题的解为止，然后通过这个解推到出原问题的答案。

通用模式

分治策略通常遵循这样的通用模式，解决规模为 n 的问题，就分解成 a 个规模为 \frac{n}{b} 的子问题，然后在 O(n^d) 时间内将子问题的解给合并起来。

总结下来，算法运算的时间 T(n) = aT(\frac{n}{b}) + O(n^d)，a > 0，b > 1，d \geq 0。 继续简化运算时间的公式，有以下三个公式：

• d < logb^a，T(n) = O(n^d)；
• d = logb^a，T(n) = O(n^dlogn)；
• d < logb^a，T(n) = O(n^(logb^a))

求最大连续子序列和

接下来通过求最大连续子序列和来进一步了解下分治策略。

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

子串、子数组、子区间是连续的，子序列是可以不连续的。

那么最简单的实现，就是暴力求解，找出所有连续子序列的和，比较出最大的那个。如下代码所示，用三个 for 循环来找出所有的连续子序列，并比较出最大值。

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++) { int sum = 0; for (int i = begin; i <= end; i++) { sum += nums[i]; } max = Math.max(max, sum); } } return max; }

看上面的代码，可以计算出空间复杂度是 O(1)，时间复杂度是 O(n^3)。函数中可以继续优化，重复使用前面计算出的 sum 值，代码如下所示：

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)，时间复杂度减少为 O(n^2)。

分治求最大子序列和

现在用分治策略来求最大子序列和。先将序列均匀的分割成两个子序列 [begin, end) = [begin, mid) + [mid, end)，mid = (begin + end) >> 1。

‘[‘ 表示大于并等于

‘)’ 表示小于

假设 [begin, end) 的最大子序列是 S[i, j)，那么它就有三种可能情况：

1. S[i, j) 在 [begin, mid) 中；
2. S[i, j) 在 [mid, end) 中；
3. S[i, j) 一部分在 [begin, mid) 中，一部分在 [mid, end) 中。

当出现第3种情况时，继续往下分析：

1. [i, j) = [i, mid) + [mid, j)，公式成立；
2. S[i, mid) = max{S[k, mid)}，begin <= k < mid；
3. S[mid, j) = max{S[mid, k)}，mid <= k < end；

所以用代码实现时，就是将这三种情况都给求解出来，然后比较这3种情况的解，其中最大的就是这个序列的连续子序列和。

先创建一个对外调用的函数，设置 nums 数组异常的处理，如下代码所示：

static int maxSubArray(int[] nums) { if (nums == null || nums.length == 0) return 0; return maxSubArray(nums, 0, nums.length); }

然后创建一个求连续子序列和的函数，传入 nums 的同时，也要传入 begin 和 end，在这个函数中要实现 S[i, j) 的三种情况，第一种情况用 maxSubArray(nums, begin, mid) 处理，第二种情况用 maxSubArray(nums, mid, end) 来处理。这种处理方式就是递归思想。

最后处理第三种情况，那么就要分别求解出 [i, mid) 和 [mid, j）中的连续子序列和，因为第三种情况是分布在 mid 左右，并且是连续的，所以这种情况的连续子序列的和就是 leftMax + rightMax。如下代码所示：

static int maxSubArray(int[] nums, int begin, int end) { if (end - begin < 2 return numsbegin int mid='(begin' end>> 1; int leftMax = Integer.MIN_VALUE; int leftSum = 0; for (int i = mid-1; i >= begin; i--) { leftSum += nums[i]; leftMax = Math.max(leftMax, leftSum); } int rightMax = Integer.MIN_VALUE; 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)) ); }

函数中最后的 return 后的代码就是比较这三种情况，并返回其中最大的值。因为是递归的方式，所以函数中一定要有结束递归的条件，if (end – begin < 2) return nums[begin]; 就是递归基。

通过分治策略求连续最大子序列和的空间复杂度是 O(\logn)，时间复杂度是 O(n\logn)，低于暴力求解的复杂度。

总结

• 分治策略，就是将问题拆分成规模小的子问题，并继续拆分，直到能直接得出答案后再反推导出原问题答案；
• 分治策略更适合使用递归思想；
• 求序列中的最大子序列和，使用分治能降低空间和时间复杂度。