算法基础 | 递归与分治

递归与分治策略

分治与递归经常同时应用在算法设计中

递归（Recursion）

递归算法—直接或间接地调用自身的较小模式的算法
递归函数—用函数自身的较小模式给出其定义的函数

example1:Fibonacci Series

Code1:

fibonacci(int n)
{
    if(n<=1) return 1;//递归边界
    else return fibonacci(n-1)+fibonacci(n-2);//递归方程
}

时间复杂度:T(n)=sqrt(2)^n
时间复杂度过高的原因：存在很多重复的计算

Code2:

fibonacci(int n)
{
    int f[3]={1,1};
    
    for(i=0;i<=n;i++)
    {
        f[2]=f[0]+f[1]; f[0]=f[1]; f[1]=f[2];
    }
    
    return f[2];
}

时间复杂度：O(n)

设计更快的算法！！！

example2:Hanoi塔

Code:

hanoi(int n,char a,char b,char c)//T(n)=O(2^n)
{//将塔座a上的盘子移到塔座b上，塔座c为辅助塔座
    if(n>0)
    {
        hanoi(n-1,a,c,b);
        move(a,b);
        hanoi(n-1,c,b,a);
    }
}

递归小结

优点：结构清晰、可读性强—>设计算法、调试程序比较方便
缺点：程序运行效率低

分治(Divide and Conquer)

适用条件：

1. 该问题的规模缩小到一定程度就可以容易地解决
2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
3. 该问题分解出的子问题的解可以合并为该问题的解
4. 该问题分解出的各个子问题是相互独立的（子问题之间不包含公共的子问题）

基本步骤：

divide-and-conquer(p)
{
    if(|p|<=n0) naive(p);//解决朴素问题
    divide p into smaller p1,p2...pa//分解问题
    for(i=1;i<=a;i++)
    {
        yi=divide-and-conquer(pi);//递归的解各子问题
    }
    return merge(y1,y2...ya);将子问题的解合并为原问题解
}

Note:
在用分治法设计算法时，最好使子问题的规模大致相同(将一个问题分为大小相等的a个子问题的处理方法是行之有效的)。
这种做法出自平衡子问题的思想

example1:Binary Search Algorithm

Code:

binarySearch(int a[],int x)//T(n) = O(logn)
{
    int n = sizeof(a),left = 0,right = n-1;
    
    while (left<=right)
    {
        int middle = (left+right)/2;
        if(x == a[middle]) return middle;
        if(x>a[middle]) left = middle + 1;
        else right = middle-1;
    }
    
    return -1;//x not found
}

example2:Powering a number

Problem:Compute a^n,where n is subjected to N.
Naive algorithm:O(n)
Divide-and-conquer algorithm:
Code:

power(int a,int n)//T(n)=O(logn)
{
    if(n==1) return a;
    else if(n%2==0) return power(a,n/2)*power(a,n/2);
    else return power(a,(n-1)/2*power(a,(n-1)/2*a);
}