分治法

在计算机科学中,分治法(Divide and Conquer)是建基于多项分支递归的一种很重要的算法范式。

字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并

这个技巧是很多高效算法的基础,如排序算法(归并排序、快速排序)、傅立叶变换(快速傅立叶变换)、施特拉森算法(Strassen algorithm)

分治算法是一个解决复杂问题的好工具,它可以把问题分解成若干个子问题,把子问题逐个解决,再组合到一起形成大问题的答案

分治法跟 动态规划 很像,但是分治法不处理重叠子问题的情况,如果有严重的重复处理子问题的情况,则不应该用分治法去解


分治法循环递归实现:

分解:将原问题分解为若干个规模较小,相对独立,与原问题形式相同的子问题

解决:若子问题规模较小且易于解决时,则直接解。否则,递归地解决各子问题

合并:将各子问题的解合并为原问题的解。


下面是利用分治法求x的n次幂 pow(x,n)

/* Function to calculate x raised to the power y in O(logn)*/
int power(int x, unsigned int y) 
{ 
    int temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2); 
    if (y%2 == 0) 
        return temp*temp; 
    else
        return x*temp*temp; 
}


上一篇: A*算法-自动寻路
下一篇: 平面最近点对
作者邮箱: 203328517@qq.com