跳到主要内容

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 的同时,也要传入 beginend,在这个函数中要实现 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、总结

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