初学算法-----分而治之-为何分治有更快的速度

本文主要是介绍初学算法-----分而治之-为何分治有更快的速度，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

以下内容转载自一个大佬cutter_point的:

关于分治算法是这样定义的:

为解决一个给定的问题, 算法需要一次或多次的递归调用其自身来解决相关的子问题.即我们把一个大规模的问题划分为n个规模较小的而结构与原来相似的子问题,递归解决这些子问题,然后再合并其结果。这样就得到了最终的结果。

从步骤上来讲, 可以分为三步:

1. 分解(Divide): 将一个问题为N的问题分解成一系列子问题。

2. 解决(Conquer): 递归的处理每个子问题.如果子问题足够小,则直接给出解。

3. 合并(Combine): 把每个已经处理好的子目问题合并,得到最终的解。

递归调用时, 最关键的就是递归调用栈的深度. 我们也可以理解为分治算法中,被分成的段数。 也就是步骤中的第1步中所分成的子序列的个数。 假设这个递归调用深度我们用 D(n)来表示。

另外一个就是在每次处理一个具体子序列时，所用的时间复杂度，我们用C来表示。

则最终的这个函数的时间复杂度为：

 C *D(n) 

对于D(n):每次分治的算法都是把序列分成两部分， 在最优的情况下，即每次都分成两等份，那它的问题子序列个数就是Log₂N 个，那在最好情况下的时间复杂度就可以理解为Ѳ（NLog₂N）;

而像普通的递归:

汉诺塔。

递归函数一般这样写：

void hanoi(int n,char one ,chartwo,char three)

　    if(n==1)  move(one,three);

　　  else{undefined
 　　  hanoi(n-1,one,three,two);  // 需要递归n-1次的移动
 　　  move(one,three);          //  只需要移动1次
 　　  hanoi(n-1,two,one,three); //  需要 递归n-1次移动
　　  }

   }

   它时间效率又是怎么样的呢？

   从这里看，第一次的移动接口是一个常数，我们就可以认为是Ѳ（1）了，那它的递归层数是多少呢？

   很明显，每一次的调用都是减1的，且要移动两次，如上面标识我们可以得出递推公式：

           C_n+1 = 2C_n + 1 , 当n为1时,C₁ = 1

    => C_n =  2^n-1  -1 。

    Cn+1 = 1 +2Cn

      = 1 + 2 + 2²Cn-2

      = 1 + 2 + 2² + 2³ + ... +2^n-1C₁ 

        这个为 首项为1,末项为2^n-1C₁ 比例系数为2的等比数列求和.

      = 1(1-2^n-1)/(1-2) = 2^n-1 - 1

 即 Ѳ （2ⁿ）。很大啊~~~~~ 

这篇关于初学算法-----分而治之-为何分治有更快的速度的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！