19、数据结构与算法 - 实战:分治
摘要
分治就是将原问题不断拆分成规模小的问题,直到小问题可以得出答案为止,然后再往上推导出原问题的答案。拆分的问题必须要和原问题结构是一致,这和递归的解答思路较大程度上是一致的。
分治,可以理解为分而治之,核心逻辑就是将原问题分解成若干个小问题,原问题和小问题在结构上是一致的,唯一的区别就是规模不同。然后再将小问题分解出更小的问题,直到无法再分解为止,也就是可以直接或者简单的计算得出问题的答案。最后利用小问题推导出原问题的解。
这个和递归的思想类似,所以分治策略非常适合使用递归来处理,需要特别注意的是,分治策略中的子问题都是相互独立的。
可以应用到分治策略的有快速排序、归并排序和大数乘法等。
递归思想的拆解问题和求解
递归的思想就是将规模大的问题,拆分成规模较小的同类问题,然后将规模较小的问题再拆分成规模更小的同类问题,直到可以直接得出问题的解为止,然后通过这个解推到出原问题的答案。
1、通用模式
分治策略通常遵循这样的通用模式,解决规模为 n 的问题,就分解成 a 个规模为 n b \frac{n}{b} bn 的子问题,然后在 O( n d n^d nd) 时间内将子问题的解给合并起来。
总结下来,算法运算的时间 T(n) = aT( n b \frac{n}{b} bn) + O( n d n^d nd),a > > > 0,b > > > 1,d ≥ \geq ≥ 0。 继续简化运算时间的公式,有以下三个公式:
- d < < < l o g b a logb^a logba,T(n) = O( n d n^d nd);
- d = l o g b a logb^a logba,T(n) = O( n d l o g n n^dlogn ndlogn);
- d < l o g b a logb^a logba,T(n) = O( n ( l o g b a ) n^(logb^a) n(logba))
2、求最大连续子序列和
接下来通过求最大连续子序列和来进一步了解下分治策略。
当给定一个长度为 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 n^3 n3)。函数中可以继续优化,重复使用前面计算出的 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 n^2 n2)。
3、分治求最大子序列和
现在用分治策略来求最大子序列和。先将序列均匀的分割成两个子序列 [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≤\leq≤k<<<mid;
3、 S[mid,j)=max{S[mid,k)},mid≤\leq≤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 nums[begin];
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( log \log logn),时间复杂度是 O(n log \log logn),低于暴力求解的复杂度。
4、总结
- 分治策略,就是将问题拆分成规模小的子问题,并继续拆分,直到能直接得出答案后再反推导出原问题答案;
- 分治策略更适合使用递归思想;
- 求序列中的最大子序列和,使用分治能降低空间和时间复杂度。