算法设计及实验报告

《算法设计及实验报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、算法设计及实验报告实验报告1递归算法一、实验目的掌握递归算法的基本思想；掌握该算法的时间复杂度分析；二、实验环境电脑一台，TurboC运行环境三、实验内容、步骤和结果分析以下是四个递归算法的应用例子：用C语言实现1.阶乘：main(){inti,k;scanf("%d",&i);k=factorial(i);printf("%d",k);}intfactorial(intn){ints;if(n==0)s=1;elses=n*factorial(n-1);//执行n-1次returns;}阶乘的递

2、归式很快，是个线性时间，因此在最坏情况下时间复杂度为O(n)。2.Fibonacci数列：main(){inti,m;scanf("%d",&i);m=fb(i);printf("%d",m);}intfb(intn){ints;if(n<=1)return1;elses=fb(n-1)+fb(n-2);returns;}Fibonacci数列则是T(n)=T(n-1)+T(n-2)+O(1)的操作，也就是T(n)=2T(n)+O(1),由递归方程式可以知道他的时间复杂度T(n)是O(2n)，该数列的

3、规律就是不停的赋值，使用的内存空间也随着函数调用栈的增长而增长。1.二分查找（分治法）#include#defineconst8main(){inta[]={0,1,2,3,4,5,6,7,8,9};intn=sizeof(a);ints;s=BinSearch(a,const,n);printf("suochadeshushidi%dge",s);}BinSearch(inta[],intx,intn){intleft,right,middle=0;left=0;right=n-1;w

4、hlie(left<=right){middle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle+1;elseright=middle-1;}return-1;}二分搜索算法利用了元素间的次序关系，采用分治策略，由上程序可知，每执行一次while循环，数组大小减少一半，因此在最坏情况下，while循环被执行了O（logn）次。而循环体内部只需运算O（1）的时间，因此该算法在最坏情况下的时间复杂度为O（logn+1

5、），即O（logn）。2.合并排序（分治法）MergeSort(intlow,inthigh,int*array){intmiddle=(high+low)/2;//将数组划分为2分if(low

6、ue;}HeBing(intlow1,inthigh1,intlow2,inthigh2,int*array){int*temp,i=low1,j=low2,k=0;temp=(int*)malloc((high2-low1+1)*sizeof(int));//temp用于临时存储合并后的数组while(i<=high1&&j<=high2)//对两个有序数组进行合并{if(array[i]

7、;j++;}}if(i<=high1){while(i<=high1)temp[k++]=array[i++];}else{while(j<=high2)temp[k++]=array[j++];}for(i=low1,j=0;i<=high2;i++,j++)//将合并后的数组,复制到array中{array[i]=temp[j];}free(temp);returntrue;}这是一种分治算法。是先进行长度为1的排序，再合并成长度为2的排序，递归直到长度为n。而快速排序是先进行划分，然后排序，不需要额

8、为的空间，合并排序需要N的额外空间。是一种稳定的排序。将数组划分为小数组,通过局部的有序合并,解决问题。算法平均时间复杂度:O(nlogn)递归算法的时间复杂度求法：用通用公式：T(n)=f[T（n-1）]  f(x)是递归函数的时间复查性函数！  如下面这个简单递归是：  void Digui()  {   1-----;/*假设该语句的复查性是a*/   2----------;/*假设该语句的复查性是b*/   for(