详解分治算法

references:

分治算法详解

分治算法总结

概念

字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

如果原问题可分割成k个子问题，1 ，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法

适用条件

该问题的规模缩小到一定的程度就可以容易地解决
该问题可以分解为若干个规模较小的相同问题。(该条件反映了递归思想的存在，但不一定是最优子结构)
利用该问题分解出的子问题的解可以合并为该问题的解；
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

备注：

3)是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。
4)涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

解题步骤

分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
合并：将各个子问题的解合并为原问题的解。

一般算法设计模式如下：

 Divide-and-Conquer(P) 1. if |P|≤n0 2. then return(ADHOC(P)) 3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk 4. for i←1 to k 5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi 6. T ← MERGE(y1,y2,...,yk) △ 合并子问题 7. return(T)

|P|表示问题P的规模；
n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。
ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。
算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,…,Pk的相应的解y1,y2,…,yk合并为P的解。

summary

时间复杂度

其中C(n)是合并(combine)，D(n)是分解(divide)所需的时间复杂度

一般这种情况根据master theorem即可得到答案，具体可以参看我在进入搜索「主定理」中做的总结

分治法-动态规划联系

references：

动态规划和分治法的区别

递归，分治算法，动态规划和贪心选择的区别

相同点

大问题可以分解为若干个子问题
子问题更容易求解

====> 动态规划是分治+解决子问题冗余

不同点

个人的一点看法，在很多博客中都讲到分治是自顶向下，dp是自底而上，当然这种说法没有什么大毛病，但容易误导初学者，在看到下面这张图中的分治是先选择再解决子问题，dp是先解决子问题再选择之后才更容易让人理解

基于分治算法的一些「有名」算法

快排和归并排序

详情参考我的另一篇总结:javascript排序算法

快速排序
归并排序

汉诺(Hanoi)塔问题

references:

汉诺塔问题

汉诺塔问题以及时间复杂度

引入

该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置n个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

思路分析

首先要想达到最终将所有的盘子从A柱子移动到C柱子的目的，肯定经过了这样的三个笼统步骤：

1-n-1号盘子从A移动到B上

2. n号盘子从A移动到C上

将1-n-1号盘子从B移动到C上

显然各个子问题互相不干扰，因此可以采用分治算法，而最佳方案就是递归。

/ * T(n)=2T(n-1)+O(1) * 时间复杂度:O(2^n) */ const move=(n,x,y)=>{ 
     console.info(`take ${ 
      n} move from ${ 
      x} to ${ 
      y}`); }; const hanoi=(n,A,B,C)=>{ 
     if(n===1){ 
     move(n,A,C); }else{ 
     hanoi(n-1,A,C,B); move(n,A,C); hanoi(n-1,B,A,C); } }; // hanoi(3,'A','B','C'); hanoi(4,'A','B','C'); / take 1 move from A to B take 2 move from A to C take 1 move from B to C take 3 move from A to B take 1 move from C to A take 2 move from C to B take 1 move from A to B take 4 move from A to C take 1 move from B to C take 2 move from B to A take 1 move from C to A take 3 move from B to C take 1 move from A to B take 2 move from A to C take 1 move from B to C */

# 可以使用集中到一个函数的方式 def hanoi(n, a, b, c): if n == 1: print(a, '-->', c) else: hanoi(n - 1, a, c, b) hanoi(1, a, b, c) hanoi(n - 1, b, a, c)

时间复杂度

由 T(n)=2T(n-1)+O(1)可得时间复杂度:O(2^n)-1 取增长最快的项，即为 O(2^n)

例题

leetcode-241-为运算表达式设计优先级

可以看下面是优化后的这个题的题解，是一种分治+暂存结果的方式，但个人认为不隶属于动态规划，因为这是一个先选后解决子问题的模式

 / * optimize: 暂存每次遍历获得的数值 * @param input * @returns {[*]|[]} */ const diffWaysToCompute=input=>{ 
     let inputArr=[],symbol={ 
    '+':true,'-':true,'*':true},st=-1,map=new Map(); for(let i=0;i<input.length;i++){ 
     if (symbol[input[i]]){ 
     inputArr.push(input.slice(st+1,i)); inputArr.push(input[i]); st=i; } } inputArr.push(input.slice(st+1)); // console.info(inputArr); const diffCompute=(arr,st,ed)=>{ 
     let res=[]; if (ed-st===1&&!symbol[arr[st]]){ 
     return [Number(arr[st])]; }else{ 
     for(let i=st;i<ed;i++){ 
     if (symbol[arr[i]]){ 
     let left=map.get(`${ 
      st}-${ 
      i}`)||diffCompute(arr,st,i); let right=map.get(`${ 
      i+1}-${ 
      ed}`)||diffCompute(arr,i+1,ed); for(let j=0;j<left.length;j++){ 
     for(let k=0;k<right.length;k++){ 
     if(arr[i]==='+'){ 
     res.push(left[j]+right[k]); }else if(arr[i]==='-'){ 
     res.push(left[j]-right[k]); }else{ 
     res.push(left[j]*right[k]); } } } } map.set(`${ 
      st}-${ 
      ed}`,res); } } console.info('map===>',map); return res; }; return diffCompute(inputArr,0,inputArr.length); };

leetcode-53-最大子序和

这道题被分到分治算法的条目下，当然可以使用分治算法来解决，但是通过观察会发现，或许分割是好分的，下面主要探究如下两个问题：

用什么样的思路解决呢？
如果解决好了一个子问题，如何进行合并呢？

首先我们对测试用例[-2,1,-3,4,-1,2,1,-5,4]进行分解；
- 如果只有一个元素，那么就是它本身
- 如果有两个元素：[-2,1]，那么最大子序和是1 毫无疑问，我们如何比较的，肯定是比较：-2，1，-2+1===> 1,由此也有了我们 combine 的主体思路： Math.max(left,right,sum(left,right))
- 如果有三个元素呢？[-2,1,-3] 首先 left 肯定选定为1了 right 即为-3，此时 sum(left,right)为 -2，那么按之前的思路，最终结果为 1，正确
- 如果是四个元素呢 [-2,1,-3,4]，有关[-2,1] 即 left 为 1，有关[-3,4] 即 right 为4，最终结果是5，显然错误，如果思路没问题，那么sum(left,right)就有问题，因此将sum(left,right)重新调整计算方式，理应为左侧倒序，右侧正序的相加
  - 且在此处有一个陷阱点：是否觉得但凡遇到负数即停止遍历呢？，并不是，比如[3,0,2,-2,3]，因此应该遍历到最后
根据1中的分析可以得到如下代码

/ * 分治算法，基本思路如下：分成左右两部分，关键在于组合combine部分 * 时间复杂度: O(NlogN) * 空间复杂度: O(logN) 递归时栈所用的空间 * 注：combine 部分的函数crossSum 乍一看像是有重复计算，实则不然，每个元素都有自己的交叉和。 * @param nums * @returns {*|number} */ const maxSubArray2=nums=>{ 
     const crossSum=(arr,left,right,p)=>{ 
     if(left===right) return arr[left]; let leftSubSum=-Number.MAX_SAFE_INTEGER; let curSum=0; for(let i=p;i>left-1;i--){ 
     // 这种判断方式不对，会跳过[3,0,2,-2,3]这种情况，因此此处需要格外注意 // if(arr[i]>=0){ 
     // leftSum+=arr[i]; // }else{ 
     // break; // } curSum+=arr[i]; leftSubSum=Math.max(leftSubSum,curSum); } let rightSubSum=-Number.MAX_SAFE_INTEGER; curSum=0; for(let i=p+1;i<right+1;i++){ 
     curSum+=arr[i]; rightSubSum=Math.max(rightSubSum,curSum); } return leftSubSum+rightSubSum; }; const helper=(arr,left,right)=>{ 
     if(left===right){ 
     return arr[left]; } // 分解 let p=Math.floor((left+right)/2); // 解决 let leftSum=helper(arr,left,p); let rightSum=helper(arr,p+1,right); // 合并 let crossSum0=crossSum(arr,left,right,p); console.info('===>',leftSum,rightSum,crossSum0); return Math.max(leftSum,rightSum,crossSum0); }; return helper(nums,0,nums.length-1); };

在了解到这种计算的方式后有一点想法：是否可以直接通过求交叉和的方式将答案求出呢，那么现在试验一下：

下图中：left每个元素是倒序的leftSubSum。right每个元素是正序的 rightSubSum,可以发现按图示箭头相加即为随意按某个值分割之后的交叉和，得到[-1,2,2,5,6,3,2,0] 其中取最大值即为6.

详解分治算法

但是问题来了，求 left 和 right 集合实则时间复杂度为n^2，最终又跳出了暴力解的方式，故不可取。

Kadane algorithm

kadane algorithm实质上是一种动态规划算法，

状态转移方程：F(n)=f(n)+F(n-1)>0?F(n-1):0;

最优子结构：F(n-1) 显然就是前面 n-1 个序列的子序列最大和，

但同时我们需要暂存这些结果避免重复计算

# kadane 伪代码 cur, res = 0, -sys.maxsize-1 for x in nums: cur = x + max(cur, 0) # res 实际上是在暂存 cur res = max(res, cur)

当然这道题用分治算法来做未免有点稍微难绕，这样思考这个问题，我们想要求得的永远都是连续的子序列的和，因此可以求出每一个元素到该元素为止的最大和

/ * 时间复杂度:O(n) * 空间复杂度:O(1) * @param nums * @returns {*} */ const maxSubArray=nums=>{ 
     let res=nums[0]; for(let i=1;i<nums.length;i++){ 
     if(nums[i-1]>0){ 
     nums[i]+=nums[i-1] } res=Math.max(res,nums[i]); } // console.info(nums); return res; };

leetcode-169-多数元素

这道题非常简单，但我当时用分治法并没有做出来，也总结了一下没做出来的原因，总是力求更简单而无法保证最稳妥的方法，而私以为分治算法的难点恐怕就在于combine合并环节，因此单独拿出这个题做分治算法的examples讲解，也希望自己能更好的加深印象。

下面总结了两个我的常犯错误：

曾试图降级到只有两个元素，显然不对，应该最终都降级为一个元素
combine的时候未能囊括所有情况（定位不准）

/ 时间复杂度: T(n)=2T(n/2)+2n * 根据master theorem * a=2 b=2 f(n)=2n 符合第二种情况，O(n)=nlogn; * 尽管分治算法没有直接分配额外的数组空间，但因为递归的过程， * 在栈中使用了一些非常数的额外空间。 * 因为算法每次将数组从每一层的中间断开，所以数组长度变为 1 之前只有 O(lgn)次切断。 * 由于递归树是平衡的，所以从根到每个叶子节点的长度都是 O(lgn)。 * 由于递归树是深度优先的，空间复杂度等于最长的一条路径，也就是 O(lgn)。 * @param nums * @returns {*} */ const majorityElement2=nums=>{ 
     const count=(arr,num,left,right)=>{ 
     let count=0; for(let i=left;i<=right;i++){ 
     if(arr[i]===num){ 
     count++; } } return count; }; const conquer=(arr,left,right)=>{ 
     if(left===right){ 
     return arr[left]; } let mid=Math.floor((left+right)/2); let leftRes=conquer(arr,left,mid); let rightRes=conquer(arr,mid+1,right); // console.info(leftRes,rightRes); if(leftRes===rightRes){ 
     return leftRes; } return (count(arr,leftRes,left,right)>count(arr,rightRes,left,right)?leftRes:rightRes); }; return conquer(nums,0,nums.length-1); };

leetcode-932-漂亮数组

references:

官方题解

 / * 易错点1： 对于N个数，奇数有多少个，偶数有多少个，奇数floor((N+1)/2) 偶数floor(N/2) * 易错点2： 映射关系是否可以定为2*x+1呢，可以，但是会不符合题意，超出N的范围 * 总结：该题不易做，很难想到利用奇偶两侧满足的 * @param {number} N * @return {number[]} */ const beautifulArray = N=> { 
     let map=new Map(); const helper=num=>{ 
     if(num===1){ 
     map.set(1,[1]); return [1]; } if(map.has(num)){ 
     return map.get(num); } let t=0,res=[]; for(let i of helper(Math.floor((num+1)/2))){ 
     // res[t++]=2*i-1; } for(let i of helper(Math.floor(num/2))){ 
     res[t++]=2*i; } map.set(num,res); return res; }; return helper(N); };

summary

对于这种毫无头绪的题目，有时候需要盯着题目中的表达式寻找出路，比如对于A[k] * 2 = A[i] + A[j]可以联想到寻找奇偶数的方向（虽然这很难想

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/224402.html原文链接：https://javaforall.net

详解分治算法