首页 > 专题系列 > 算法分析 > 递归与分治策略(2)
2013
12-26

递归与分治策略(2)

整数划分问题 

将正整数n表示成一系列正整数之和:n=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。

正整数n的这种表示称为正整数n的划分。正整数n的不同划分个数称为正整数n的划分数,记作p(n)。

例如正整数6有如下11种不同的划分,所以p(6) = 11:

    6;

    5+1;

    4+2,4+1+1;

    3+3,3+2+1,3+1+1+1;

    2+2+2,2+2+1+1,2+1+1+1+1;

1+1+1+1+1+1。

前面的几个例子中,问题本身都具有比较明显的递归关系,因而容易用递归函数直接求解。

在本例中,如果设p(n)为正整数n的划分数,则难以找到递归关系,因此考虑增加一个自变量:在正整数n的所有不同划分中,将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。

(1) q(n,1)=1,n >= 1;当最大加数n1不大于1时,任何正整数n只有一种划分形式,

即n = 1 + 1 + 1 + … +1.

(2) q(n,m) = q(n,n),m >= n; 最大加数n1实际上不能大于n。因此,q(1,m)=1。(3) q(n,n)=1 + q(n,n-1); 正整数n的划分由n1=n的划分和n1 ≤ n-1的划分组成。

(4) q(n,m)=q(n,m-1)+q(n-m,m),n > m >1;正整数n的最大加数n1不大于m的划分由 n1 = m的划分和n1 ≤ m-1  的划分组成。

前面的几个例子中,问题本身都具有比较明显的递归关系,因而容易用递归函数直接求解。

在本例中,如果设p(n)为正整数n的划分数,则难以找到递归关系,因此考虑增加一个自变量:将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。

q(n,m) = 1                  n = 1, m = 1

q(n,m) = q(n,n)                n = 1, m = 1

q(n,m) = 1 + q(n,n-1)         n = m

q(n,m) = q(n,m-1) + q(n-m,m)  n > m > 1

正整数n的划分数p(n) = q(n,n)。

实现:

 

/* 主题:整数划分使用递归实现
* 作者:chinazhangjie
* 邮箱:[email protected]
* 开发语言:C++
* 开发环境:Code::Blocks 10.05
* 时间: 2010.10.07
*/
#include <iostream>
using namespace std;

//
int __int_partition(int n,int m)
{
    if (n < 1 || m < 1)
        return 0;
    if (n == 1 || m == 1)
        return 1;
    if (n < m)
        return __int_partition(n,n);
    if (n == m)
        return __int_partition(n,m - 1) + 1;
    return __int_partition(n,m - 1) + __int_partition(n - m,m);
}
int integer_partition(int n)
{
    return __int_partition(n,n);
}

int main()
{
    for (int i = 1; i < 7; ++ i) {
        cout << "integer_patition("
             << i
             << ") = "
             << integer_partition(i)
             << endl;
    }
    return 0;
}

 

例6       Hanoi塔问题

设a,b,c是3个塔座。开始时,在塔座a上有一叠共n个圆盘,这些圆盘自下而上,由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上,并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则:

规则1:每次只能移动1个圆盘;

规则2:任何时刻都不允许将较大的圆盘压在较小的圆盘之上;

规则3:在满足移动规则1和2的前提下,可将圆盘移至a,b,c中任一塔座上。

实现:

 

/* 主题:hanoi使用递归实现
* 作者:chinazhangjie
* 邮箱:[email protected]
* 开发语言:C++
* 开发环境:Code::Blocks 10.05
* 时间: 2010.10.07
*/

#include <iostream>
using namespace std;


void __move(char t1,char t2)
{
    cout << t1 << " -> " << t2 << endl;
}
// 把n个圆盘,从t1塔移至t2塔通过t3塔
void hanoi(int n,char t1,char t2,char t3)
{
    if (n > 0) {
        hanoi(n-1,t1,t3,t2);
        __move(t1,t2);
        hanoi(n-1,t3,t2,t1);
    }
}

int main()
{
    cout << "hanoi(1,'a','b','c'): " << endl;
    hanoi(1,'a','b','c');
    cout << endl;

    cout << "hanoi(1,'a','b','c'): " << endl;
    hanoi(2,'a','b','c');
    cout << endl;

    cout << "hanoi(3,'a','b','c'): " << endl;
    hanoi(3,'a','b','c');
    cout << endl;

    return 0;
}

递归小结

优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便。

缺点:递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

解决方法:在递归算法中消除递归调用,使其转化为非递归算法。

1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强,但本质上还是递归,只不过人工做了本来由编译器做的事情,优化效果不明显。

2、用递推来实现递归函数。

3、通过变换能将一些递归转化为尾递归,从而迭代求出结果。

后两种方法在时空复杂度上均有较大改善,但其适用范围有限。

分治法的适用条件

分治法所能解决的问题一般具有以下几个特征:

1、该问题的规模缩小到一定的程度就可以容易地解决;

2、该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质

3、利用该问题分解出的子问题的解可以合并为该问题的解;

4、该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。(这条特征涉及到分治法的效率,如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然也可用分治法,但一般用动态规划较好。)

分治法的基本步骤

divide-and-conquer(P)

{

    if (|P| <= n0) adhoc(P);   // 解决小规模的问题

    divide P into smaller subinstances P1,P2,…,Pk;//分解问题

    for (i=1,i<=k,i++)

      yi=divide-and-conquer(Pi);  //递归的解各子问题

    return merge(y1,…,yk);  //将各子问题的解合并为原问题的解

}

人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想,它几乎总是比子问题规模不等的做法要好。

分治法的复杂性分析

一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。设分解阀值n0=1,且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P| = n的问题所需的计算时间,则有:

通过迭代法求得方程的解:

二分搜索技术

给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。

分析:

1、该问题的规模缩小到一定的程度就可以容易地解决;

2、该问题可以分解为若干个规模较小的相同问题;

3、分解出的子问题的解可以合并为原问题的解;

4、分解出的各个子问题是相互独立的。

很显然此问题分解出的子问题相互独立,即在a[i]的前面或后面查找x是独立的子问题,因此满足分治法的第四个适用条件。

二分搜索实现:

 

/* 主题:二分搜索
* 作者:chinazhangjie
* 邮箱:[email protected]
* 开发语言:C++
* 开发环境:Code::Blocks 10.05
* 时间: 2010.10.07
*/
#include <iostream>
using namespace std;

// 查找成功返回value索引,查找失败返回-1
template <class T>
int binary_search(T array[],const T& value,int left,int right)
{
    while (right >= left) {
        int m = (left + right) / 2;
        if (value == array[m])
            return m;
        if (value < array[m])
            right = m - 1;
        else
            left = m + 1;
    }
    return -1;
}

int main()
{
    int array[] = {0,1,2,3,4,5,6,7,8,9};

    cout << "0 in array position: " << binary_search(array,0,0,9) << endl;
    cout << "9 in array position: " << binary_search(array,9,0,9) << endl;
    cout << "2 in array position: " << binary_search(array,2,0,9) << endl;
    cout << "6 in array position: " << binary_search(array,6,0,9) << endl;
    cout << "10 in array position: " << binary_search(array,10,0,9) << endl;

    return 0;
}

 

算法复杂度分析:

每执行一次算法的while循环, 待搜索数组的大小减少一半。因此,在最坏情况下,while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间,因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。

大整数的乘法

请设计一个有效的算法,可以进行两个n位大整数的乘法运算

小学的方法:O(n^2) 效率太低

分治法:

X = a b;

Y = c d;

X = a*2^(n/2) + b    Y = c*2^(n/2) + d

X*Y = a*c*2^n + (a*d + b*c)*2^(n/2) + b*d

算法复杂度分析:

T(n) = O(1) n = 1

T(n) = 4T(n/2) + O(n) n > 1

T(n) = O(n^2)     没有改进

为了降低时间复杂度,必须减少乘法的次数

(1)X*Y = a*c*2^n + ((a-b)(d-c)+ac+bd)*2^(n/2) + b*d

(2)X*Y = a*c*2^n + ((a+b)(d+c)-ac-bd)*2^(n/2) + bd

细节问题:两个XY的复杂度都是O(nlog3),但考虑到a+b,d+c可能得到n+1位的结果,使问题的规模变大,故不选择第2种方案。

算法复杂度分析:

T(n) = O(1) n = 1

T(n) = 3T(n/2) + O(n) n > 1

T(n) = O(n^log3)  = O(n^1.59)  较大的改进

小学的方法:O(n^2)            效率太低

分治法: O(n^1.59)             较大的改进

更快的方法?? 如果将大整数分成更多段,用更复杂的方式把它们组合起来,将有可能得到更优的算法。

Strassen矩阵乘法

对于两个n*n的矩阵A,B,求其乘积

传统方法:O(n^3)

A和B的乘积矩阵C中的元素C[i,j]定义为

若依此定义来计算A和B的乘积矩阵C,则每计算C的一个元素C[i][j],需要做n次乘法和n-1次加法。因此,算出矩阵C的个元素所需的计算时间为O(n^3)

分治法:

使用与上例类似的技术,将矩阵A,B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为:

由此可得:

算法复杂度分析

T(n) = O(1) n = 2

T(n) = 8T(n/2) + O(n^2) n > 2

T(n) = O(n^3)

为了降低时间复杂度,必须减少乘法的次数。

算法复杂度分析

T(n) = O(1) n = 2

T(n) = 7*T(n/2) + O(n^2) n > 2

T(n) = O(n^log7) = O(n^2.81) 较大的改进

更快的方法??

Hopcroft和Kerr已经证明(1971),计算2个2×2矩阵的乘积,7次乘法是必要的。因此,要想进一步改进矩阵乘法的时间复杂性,就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究3×3或5×5矩阵的更好算法。

在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n^2.376)

是否能找到O(n^2)的算法?

 

参考资料 《算法设计与分析基础》  王晓东 编著

授课教师 张阳教授

转自:http://www.cnblogs.com/chinazhangjie/archive/2010/10/07/1845159.html


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  2. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  3. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  4. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。