以下内容转载自一个大佬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
=> Cn = 2n-1 -1 。
Cn+1 = 1 +2Cn
= 1 + 2 + 22Cn-2
= 1 + 2 + 22 + 23 + ... +2n-1C1
这个为 首项为1,末项为2n-1C1 比例系数为2的等比数列求和.
= 1(1-2n-1)/(1-2) = 2n-1 - 1
即 Ѳ （2n）。很大啊~~~~~