【算法复习四】计算复杂性与算法分析---算法分析

一，生成函数与递推

递推关系举例

【例1】Hanoi问题：这是个组合数学中的著名问题。N个圆盘依其半径大小，从下而上套在A柱上，如下图示。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要移动几个盘次。现在只有A、B、C三根柱子可用。

| | |

| | |

A B C

第一步把A中N-1个移动到B(借助C)

第二步把A中最下一个移动到C

第三步把B中移动到C(借助A)

算法复杂度：

h(n)表示n个盘子所需要转移次数。

h(n)=2h(n-1)+1

h(1)=1

递归算法：

#include <iostream> 
using namespace std; 

int num=0;

void Move(int n,char x,char y) 
{ 
   num++;
   cout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl; 
} 
void Hannoi(int n,char a,char b,char c)//把n个盘子从a移动到c 借助b 
{ 
     if(n==1) 
         Move(1,a,c); 
     else 
     { 
         Hannoi(n-1,a,c,b); //把n-1个盘子从a移动到b 借助c

         Move(n,a,c); 
         Hannoi(n-1,b,a,c); //把n-1个盘子从b移动到c 借助a
     } 
} 
int main() 
{ 
     cout<<"以下是 3 层汉诺塔的解法:"<<endl; 
     Hannoi(7,'a','b','c'); 

     cout<<"输出完毕!共需要次数："<<num<<" 次"<<endl; 
     return 0; 
} 

【例2】排错问题.n个有序的元素应有个不同的排列，如若一个排列使得所有的元素都不在原来的位置上，则称这个排列为错排；有的叫重排。

以1，2，3，4四个数的错排为例，分析其结构，找出规律性的东西来。

1）1 2的错排是唯一的，即2 1。

2）1 2 3的错排有3 1 2，2 3 1。这二者可以看作是1 2错排，3分别与1，2换位而得的。

即 2 1 32与3换位3 1 2

2 1 3 1与3换位2 3 1

3）1，2，3，4的错排

4 3 2 1，4 1 2 3，4 3 1 2，

3 4 1 2，3 4 2 1，2 4 1 3，

2 1 4 3，3 1 4 2，2 3 4 1。

第一列是4分别与1，2，3互换位置，其余两个元素错排，由此生成的。

第二列是4分别与3，1，2（123的一个错排）的每一个数互换而得到的

分析：

设n个数1，2，…，n错排的数目为Dn，任取其中一数 i，数i分别与其他的n-1个数之一互换，其余n-2个数进行错排，共得 (n-1)Dn-2个错排。另一部分位数i以外的n-1个数进行错排，然后 i 与其中每个数互换得(n-1)Dn-1个错排。

Dn=(n-1)(Dn-1 + Dn-2) D1=0 D2=1

Dn - nDn-1=(-1) `n

二，递归算法的结构

递归结构定义

在进行递归算法的设计时，通常先写出问题的递归定义，递归定义由基本项和归纳项两部分组成。

•基本项，也就是递归出口。它描述了一个或几个递归过程的终止状态。所谓终止状态指的是不需要继续递归而直接求解的状态。

•归纳项，也称为递归过程。它描述了如何实现从当前状态到终止状态的变化。

#include <iostream>
using namespace std;

int multiplication(int n)
{
	if(n==1)
		return 1;
	return n*multiplication(n-1);
}
int main()
{
	cout<<"10的阶乘为："<<multiplication(10)<<endl; 
	return 0;
} 

• 基于递归的插入排序算法

#include <iostream>
using namespace std;
void in_rec (int A[],int n)// 基于递归的插入排序算法
{ 
	 int a,k;
	 if(n<1)
	 	return ;
    
     	in_rec (A,n-1);//归纳项，否则,对前面的n-1个元素排序
      	a = A[n];  // 把第n元素插入合适位置   
        k = n -1;
        while ((k>=0)&&(A[k]>a)) 
		{
  			A[k+1] = A[k];
     		k = k - 1;
       	}
         A[k+1] = a;
} 
int main()
{
	int a[5]={3,2,1,4,5};
	in_rec (a,5);
	for(int i=0;i<5;++i)
		cout<<a[i]<<"  ";
	cout<<endl;
	return 0;
}

三，组合算法分析

1）全排列算法

•模型对应

•序数法

•字典序法
•中介数法

•换位法

例题：1 2 3 4 5 6 7 8 9 字典序全排列，求8 3 9 6 4 7 5 2 1的下一个排列

分析：一个全排列可看做一个字符串，字符串可有前缀、后缀。所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。

例如，839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。

解答： １、搜索末端的最长递降序列。
２、记紧挨着该序列左边的数为 a。
３、在该序列中从右到左寻找首个大于 a 的数记为 b。
４、交换 a、b，反转原序列被 b 换入后的新序列。

（输出全排列）算法：

#include <stdio.h> 

int n = 0; 

void swap(int *a, int *b) 
{ 
	int m; 
	m = *a; 
	*a = *b; 
	*b = m; 
} 
void perm(int list[], int k, int m) 
{ 
	int i; 
	if(k > m) 
	{ 
		for(i = 0; i <= m; i++) 
			printf("%d ", list[i]); 
		printf("\n"); 
		n++; 
	} 
	else 
	{ 
		for(i = k; i <= m; i++) 
		{ 
			swap(&list[k], &list[i]); 
			perm(list, k + 1, m); 
			swap(&list[k], &list[i]); 
		} 
	} 
} 
int main() 
{ 
	int list[] = {1, 2, 3, 4, 5}; 
	perm(list, 0, 4); 
	printf("total:%d\n", n); 
	return 0; 
} 

（输出下一个）算法：

#include <iostream>  
using namespace std;  
void swap(int* x,int* y)  
{  
    int temp;  
    temp=*x;  
    *x=*y;  
    *y=temp;  
}  
void reverse(int *first,int *last)  
{  
    --last;  
    for(;first<last;first++,last--)  
        swap(first,last);  
}    
bool nextpermutation(int* first,int* last)  
{  

    if(first==last) 
		return false; //为空  
    if(first+1==last) 
		return false; //只有一个元素  

    int* i=last;  
    --i;  //最后一个元素 
    for(;;){  
        int* ii=i; //后一个元素 
		--i;//前一个元素  
        if(*i<*ii){ //前<后且相邻  
            int* j=last;  
            while(!(*i<*--j));//从后向前找第一个大于i的数                          
            swap(i,j); //交换*i，*j  
            reverse(ii,last); //反向排列[ii,last)  
            return true;  
        }  
        if(i==first){//前一元素已指向首元素，反转整个区间，无下一排列  
            reverse(first,last);  
            return false;  
        }  
    }  
}  

//输出结果8 3 9 6 5 1 2 4 7   
int main()  
{  
    int d[]={8,3,9,6,4,7,5,2,1};  
    if(nextpermutation(d,d+9))  
    {  
        for(int i=0;i<9;i++)  
            cout<<d[i]<<" ";  
        cout<<endl;  
    }  
    return 0;  
}  
  

2）中介数

在[1,n]的全排列中,nn-1… 321是最后一个排列,其中介数是(n-1,n-2,...,3,2,1)。而其序号为 1*1！+2*2！+……（n-1)!

计算给定排列的序号

8 3 9 6 4 7 5 2 1的序号即先于此排列的排列的个数。将先于此排列的排列按前缀分类。

将8!,7!,…,1!前面的系数抽出，放在一起得到7 2 6 4 2 3 2 1。

7 2 6 4 2 3 2 1是计算排列8 3 9 6 4 7 5 2 1的序号的中间环节，我们称之为中介数。

※这是一个很有用的概念。

【例12】由中介数推出排列的算法，例如由中介数7 2 6 4 2 3 2 1(8个数)推算出全排列：8 3 9 6 4 7 5 2 1

方法一： 推导

p1 p2 p3 p4 p5 p6 p7 p8 p9

8 2 1

8 3 2 1

8 3 4 2 1

8 3 9 4 2 1

…… …… ……

其他详细方法参见博文 http://blog.csdn.net/tianshuai11/article/details/7520370