算法第2章小结

递归与分治策略

  递归:直接或间接地调用自身的算法称为递归算法。

       用函数自身给出定义的函数称为递归函数。

  【例1】Fibonacci数列

int fibonacci (int n){
    if (n <= 1 ) 
        return 1;
    return fibonacci (n - 1) + fibonacci(n - 2);
}

 

  【例2】Hanoi塔问题

 

void hanoi(int n, int a, int b, int c ){
    if(n > 0){
        hanoi(n - 1, a, c, b);
        move(a, b);
        hanoi(n - 1, c, b, a);
    }
}

 

  分治:分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。递归地解这些子问题,然后将各个子问题的解合并得到原问题的解。

 

  时间复杂度: T(n) = aT(n / b) + O(nd)      a >= 1, b > 1 为常数]

                T ( n )    =  { O(nd),             d > logba

                { O(n * log n) ,   d = logba

 

                { O(nlogba) ,          d < logba

  二分搜索技术、合并排序、快速排序等都是分治法的例子体现。其中,合并排序的基本思想是,将待排序元素分为大小大致相同的两个子集合,分别对两个子集合进行排序,最终将排好的子集合合并成要求的排好序的集合快速排序的基本思想是,分解、递归调用快速排序算法分别进行排序、合并

  

  分治策略其实可以看成是算法里的“郡县制”,先将权力分配到各个郡县,最后再归回同一到君主。如此一来,就不用事事都劳费君主处理了,便能高效地处理事务。

  结对编程其实可以看成是“三英战吕布”,同小伙伴一起攻下问题,一同学习一同进步,岂不妙哉!

 

你可能感兴趣的