算法-分治算法

妖狐艹你老母 2024-04-08 10:08 228阅读 0赞

### 一、分治 ###

#### 1、定义：分治，也就是分而治之。 ####

#### 它的一般步骤是： ####

① 将原问题分解成若干个规模较小的子问题（子问题和原问题的结构一样，只是规模不一样）

② 子问题又不断分解成规模更小的子问题，直到不能再分解（直到可以轻易计算出子问题的解）

③ 利用子问题的解推导出原问题的解

> 分治策略非常适合用递归

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

#### 2、分治的应用 ####

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

#### 3、分治时间复杂度的计算–主定理 ####

![800d948f368a29f98792b4e349627502.png][]

#### 4、最大连续子序列和 ####

子序列：按照原序列的排序顺序，从原序列取出部分元素

连续子序列：按照原序列的排序顺序，连续地从原序列取出部分元素

*  举例：
    
    原序列：–2、1、–3、4、–1、2、1、–5、4
    
    子序列可以是：–2、1、1、4 还可以是：4、1、4 还可以是：2、1、–5、4 等等
    
    连续子序列可以是：–2、1、–3、4、–1 还可以是：–3、4、–1 还可以是：2、1、–5、4 等等

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

#### 解法：分治 ####

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

*  \[begin , end) = **\[begin , mid) + \[mid , end)**，mid = (begin + end) >> 1

◼ 假设 \[begin , end) 的最大连续子序列和是 S\[i , j) ，那么它有 **3 种可能**

*  \[i , j) 存在于 \[begin , mid) 中，同时 S\[i , j) 也是 \[begin , mid) 的最大连续子序列和
 *  \[i , j) 存在于 \[mid , end) 中，同时 S\[i , j) 也是 \[mid , end) 的最大连续子序列和
 *  \[i , j) 一部分存在于 \[begin , mid) 中，另一部分存在于 \[mid , end) 中
    
     *  \[i , j) = \[i , mid) + \[mid , j)
     *  S\[i , mid) = max \{ S\[k , mid) \}，begin ≤ k ＜ mid
     *  S\[mid , j) = max \{ S\[mid , k) \}，mid ＜ k ≤ end

![38acd225b5dd3a1511354b70f01d391a.png][]

> 对于解：只在左边或者只在右边，可以直接使用 递归
> 
> 对于解：在中间，一部分在左边，一部分在右边的情况：
> 
> ![091a0ff6eab1f3bc9edfa5a65b242af5.png][]
> 
>  *  需要先 从中间mid开始统计\[mid - 1, 左边某个元素\] 统计出左边的最大值
>  *  再从中间mid开始统计\[mid, 右边某个元素\] 统计出右边的最大值
>  *  然后左边最大值+右边最大值，就是 横跨两个区域的解

static int maxSubArray(int[] nums) {
        
    		if(nums == null || nums.length == 0) return 0;
    		return maxSubArray(nums, 0, nums.length);  
    	}
    
    	/** 
    	 * 分治法
    	 */
    	private static int maxSubArray(int[] nums, int begin, int end) {
        
    		if(end - begin < 2) return nums[begin];
    		int mid = (begin + end) >> 1;
    		
    		// 要从中间mid开始统计[mid - 1, 左边某个元素]、[mid, 右边某个元素]的连续最大子序列和
    		int leftMax = nums[mid - 1]; 
    		int leftSum = leftMax;
    		for(int i = mid - 2; i >= begin; i--) {
        
    			leftSum += nums[i];
    			leftMax = Math.max(leftMax, leftSum);
    		}
    		int rightMax = nums[mid];
    		int rightSum = rightMax;		
    		for(int i = mid + 1; i < end; i++) {
        
    			rightSum += nums[i];
    			rightMax = Math.max(rightMax, rightSum);
    		}
    		int midMax = leftMax + rightMax;	
    	
    		return Math.max(midMax, //中间的最大连续子序列和
    				Math.max(maxSubArray(nums, begin, mid -1), maxSubArray(nums,mid, end))); //左边、右边的最大连续子序列和
    	}

**如果本文对你有帮助的话记得给一乐点个赞哦，感谢！**

[800d948f368a29f98792b4e349627502.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/2970b32dc31e4ce3b2c43c25ee3b86f7.png
[38acd225b5dd3a1511354b70f01d391a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/c29fe886b544464fab9f143cc8a557c6.png
[091a0ff6eab1f3bc9edfa5a65b242af5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/5beb1463f523495d9561b96ea9887ccd.png