您的浏览器不支持CSS3,建议使用Firfox、Chrome等浏览器,以取得最佳显示效果

算法设计策略之分治

编程 327℃ 0 3年前 (2014-12-20)

分治,就是分而治之。简答地来说就是将一个大的问题分解成为若干小的子问题进行求解,然后将子问题的解合并得到原问题的解。好了,我们单刀直入:talk is cheap,show me the code!

首先来看最简单的fiboccina数列的例子。fiboccina数列是这样一个数列:a[1] = 1, a[2] = 1, a[3] = a[1] + a[2] …. a[n] = a[n – 2] + a[n – 1],显然这里要求a[n]就必须要求a[n – 1]和a[n – 2],而要求a[n – 1]就要先求a[n – 2]和 a[n- 3]也就是说我们必须将问题不停地划分成为子问题之后将所有子问题求出来才可以得到原问题。写出代码如下:

int fb(int num)

{

    if (num <= 2 ) /*当问题规模足够小时求解子问题*/

        return 1;

    /*分解原问题成为两个子问题,就是递归a[n] = a[n – 1] + a[n – 2]*/

    int ret = fb(num – 1) + fb(num – 2);

    return ret;

}

再上面的代码中,假设我们输入调用时fb(10),也就是求第10个fiboccina数。进入函数后,第一件事就是查看当前的问题规模是否足够小,如果小到了一定的规模(这里是1或者2)就可以解了。如果问题的规模不够小,那么继续分割,这里的10被分割成为求解a[8]和a[9]两个规模更小的子问题,于是a[8]又被分解成为a[7]和a[6]两个子问题,如此递归下去,知道问题被分割到num <= 2的规模就进行求解。这里我们注意到,子问题的求解方式和原问题的求解方式是一致的(都是调用fb函数),这也就是使用分治法的一个重要标志。好了,现在按照算法设计的一般要求,我们评估一下上述算法的性能。在每次调用fb函数的过程中,都会执行一次过程,就是“+”,画出递归树求得其算法的复杂度为O(2^n).

接着我们继续分析第二个问题:

假设有一个乱序的数列,现在将它从小到大排列起来。有很多排序方法可以用,比如冒泡法,插入排序,希尔排序,堆排序,归并排序,快速排序等等算法。现在我们看看归并排序,这个算法很好的展示了分治法的原理。

首先我们要对一个数组排序,一个很朴素的想法就是,先将数组分割成多个只有两个元素的小数组,这时候由于只有两个元素,排序很容易进行,然后将排序好的小数组进行两两合并,比如说a[7]分成{ a[0], a[1]}, {a[2],a[3]}, {a[4], a[5]} {a[6], a[7]},将这些小数组排好序后,如{ a[1], a[0]}, {a[2], a[3]}合并起来,{a[4],a[5]} {a[6], a[7]}合并起来,得到{a[1], a[0], a[2], a[3]}和{a[4], a[5], a[6],a[7]},此时这两个稍微大的数组都是已经排好序的了,最后再将 {a[1], a[0], a[2], a[3]} ,{a[4], a[5], a[6],a[7]}合并得到排序好的{a[1], a[0], a[2], a[3],a[4], a[5], a[6],a[7]}.注:两个已经排序的数组合并起来的算法是很容易实现的,读者自己试试看。

下面看代码

首先是一大堆宏,DEBUG_CHECK是用来检查入口参数的宏。INIT_RAND_ARRAY将产生的随机数装入数组中作为待排序数组。SUB_SORT对两个元素的小数组进行递增排序。

然后下来是一个合并两个已经排序数组的函数:Merge(好吧,我承认这个函数是我从网上copy的)

最后是算法的中心思想部分(看这风骚的代码风格就造是自己写的唉)

在这个函数中就是: 1 规模足够小就求解 2规模不够小就分割 3求解完成之后就合并。

注意到每个子问题都可以用相同的方法来求解的,也就是说无论是原输入的数组还是分割后的数组都是被输入merge_sort函数的,再次强调:这是使用分治法的一个重要标志。

最后画出递归树,算出来算法的复杂度是O(nlogN),其中的计算方法可以参考《算法导论》,或者你可以联系我.看吧,对比起在C语言课堂上写的冒泡排序要厉害得多了吧。hiahiahia~

总结一下吧,分治就是将原问题分解成为相同的但是规模更小的子问题进行求解(事实上很多情况是我们要求原问题就不得不求解子问题)。子问题的解方法必须跟原问题的解方法一致,所以我们可以把程序写成递归的,递归就是调用了原来的函数,比如说fiboccina数列的算法中,int ret = fb(num – 1) + fb(num – 2); 一句就是分别将num – 1, num – 2输入了fb函数,对他们使用了和原问题num的方法(main中有对num使用了fb方法fb(cnt) )。

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

0

暂无评论

评论前:需填写以下信息,或 登录

用户登录

忘记密码?