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

2021/12/20 22:19:49

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

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

 

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

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

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

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

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

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

 

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

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

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

 C *D(n) 

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

而像普通的递归:

汉诺塔。

递归函数一般这样写:

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的,且要移动两次,如上面标识我们可以得出递推公式:

           Cn+1 = 2Cn + 1 , 当n为1时,C1 = 1

    => C=  2n-1  -1 。

 

    Cn+1 = 1 +2Cn

      = 1 + 2 + 22Cn-2

      = 1 + 2 + 22 + 23 + ... +2n-1C

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

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

 即 Ѳ (2n)。很大啊~~~~~ 



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


扫一扫关注最新编程教程