分治策略

2020-04-05

分治策略

为什么采取分治策略后，性能会有所提升？

想象我们之前的冒泡排序，选择排序，插入排序。时间复杂度都是O（n^2）,到了后来我们利用分治思想采用的归并排序、快速排序，时间复杂度到了O（nlogn）.

接下来我们用案例来说明

leetcode 53、最大子序和

https://leetcode-cn.com/problems/maximum-subarray/

给定一个长度为n的整数序列，求它的最大连续子序列和

穷举所有的可能，并且计算他们的和，取最大值

static int maxSubArray(int nums[]) {
if(nums.length==0||nums==null) return 0;
		
		int max=Integer.MIN_VALUE;
		for(int begin=0;begin<nums.length;begin++) {
               for(int end=begin;end<nums.length;end++) {
            	   //[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).看来确实有必要进行优化一下

在上面第三个for循环中，我们应该做了很多次的重复操作。当end指针往后挪时，我们总是要计算begin-end之间所有值的总和，但这是不必要的。我们只需要稍加改动

static int maxSubArray(int nums[]) {
		if(nums.length==0||nums==null) 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++) {
		            	   //[begin,end]
		            	  
		            	   sum+=nums[begin];
		            	   max=Math.max(max, sum);
		            	   
		               }
				}
				return max;
			}

由于end指针在初始位置和begin在一起，并且它总是往后挪，即nums[end]相当于一直往后遍历。

经过上述优化，我们成功的将O（n^3）的复杂度变成了O（n^2）。提交到leetcode上也成功了！！！

接下来我们用分治的思想来尝试解决问题

我们将该序列均匀的分割成两个子序列[begin,end) （左闭右开）
[begin,end)=[begin,mid)+[mid,end)
假设问题的解res[i,j),即是[i,j-1]之间的所有元素，那么问题的解有三种可能

![image-20200328224754530](/Users/luojianhua/Library/Application Support/typora-user-images/image-20200328224754530.png)

1）[i,j)存在于[begin,mid)中

2）[i,j)存在于[mid,end)中

3)[i,j)一部分存在于[begin,mid)中，另一部分存在于[mid,end)中即此时[ i , j )=[i,mid)+[mid,j)

static int maxSubArray(int nums[]) {
		
		if(nums.length==0||nums==null) return 0;
		return maxSubArray(nums,0,nums.length);
		
	}
	
	/**
	 * 求解[begin,end)中最大连续子序列的和
	 * @param nums
	 * @param begin
	 * @param end
	 * @return
	 */
	static int maxSubArray(int nums[],int begin,int end) {
		//代表此时只有一个元素
		if(end-begin<2) return nums[begin];
		int mid=(begin+end)/2;
		//结合左右两边
		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)
						)
				);
		
	}

时间复杂度，由于经历了两次递归操作，和一次 for循环遍历操作

我们可以列为T(n)=2*T(n/2)+O(n).

与归并排序一摸一样，即该算法的时间复杂度为O(nlogn)。

接下来用另外一种巧妙的方法

class Solution {
    public int maxSubArray(int[] nums) {
     int res=nums[0];
     int sum=0;
     for(int num:nums){
         if(sum>0)
             sum+=num;
             else
             sum=num;
            res=Math.max(res,sum);
     }
     return res;

    }
}

上述方法的巧妙之处则在于，我们忽略了对于子序列的查找。而是根据规律来得出正确答案，试想我们最开始的的最垃圾的代码，就是对于子序列的查找，运用了O(n^2)的时间复杂度。
对于含有正数的序列而言，最大子序列肯定全部是正数，并且从头到和尾都是正数。因此我们可以从第一个正数开始算起，当当前和为负数时，我们要重新确认首项。
由于上述解法只遍历了一次数组，所以时间复杂度为O(n)。

通过本题，我们从最开始的暴力解法，然后一步步优化，引出了分治策略。当然这只是最初步的，后面我还会再详细介绍！