实验4：递归与分治策略的应用.doc

《实验4：递归与分治策略的应用.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程实验报告课程名称算法分析与设计班级实验日期姓名学号实验成绩实验名称实验4：递归与分治策略的应用实验目的及要求1．掌握分治策略的基本步骤；2．掌握分治策略的思想。实验环境操作系统：WindowsIDE：VisualC++实验内容（1）排序算法分别实现归并排序、快速排序和堆排序，输入规模N=64，128,256，512，…（N取至单次排序运行时间不超过3分钟），输入数据随机生成1-10000之间的整数，记录实验结果，做出运行时间与输入规模之间的关系曲线图，说明算法的时间复杂度和空间复杂度，根据曲线图比较3种排序算法的优劣。（2）矩阵乘法调研Strassen矩阵乘算法，随机生

2、成N*N的矩阵，矩阵中的每个数字为1-100之间的整数，N=4,8,16…（N取至单次矩阵乘时间不超过3分钟），分别用Strassen算法和你能想到的其它方法（例如直接计算）实现矩阵乘运算，做出运行时间与输入规模之间的关系曲线图，并简要分析Strassen算法和你所实现的方法的时间复杂度。调试过程及实验运行时截图：并归排序：结果运行到一定规模：快速排序：运行到一定规模：堆排序：运行到一定规模：矩阵乘法：1朴素算法：2Strassen矩阵乘算法一定规模后：总结横坐标计算规模：1：81292：655363：4：5：随着输入规模的增大，通过三种算法的时间记录做成折线图观察不难发现

3、，在初期，三种算法所用时间几乎相等，随着输入规模的不断增大，堆排序和快速排序仍然能够保持相对较小的增长，而并归排序所用时间复杂度开始大幅度增加。快速排序果然是快，数据越大优势越明显，并且实现上也较为简单。理论上它的平均时间和归并排序，堆排序都是一样的（在最坏情况还还不如它们），都是O(nlog2n)，但实际运行来看比它们两者的速度都快一倍以上。COOL！合并排序需要额外相同规模的数组，空间复杂度为O（n）。从具体实现来看，这只是一种理论上的优秀算法，想法比较简单直接，但实现上比quicksort 复杂，运行时间也差，在数据很大的时候运行时间是heapsort的两倍，更不用说

4、quicksort了。堆排序利用了二分树的结构，将时间复杂度降到O(nlog2n),理论上和实现上表现都不错,并且发现在数据量是10 000 000时，甚至优于快排，可能是运行时数据的问题。对于strassen算法对其时间复杂度分析：T（n）=7T(n/2)+O(n);而朴素算法的时间复杂度为n的三次方。随着数据增大，也出现乘方级别的时间复杂度差距。附录//头文件#include#include#include#include#include#definePARENT(i)(i/

5、2)//几个较简单函数#defineLEFT(i)(2*i+1)#defineRIGHT(i)(2*i+2)usingnamespacestd;//定义所需要变量等#defineMAXinta[MAX];//数组存储原始顺序inttemp[MAX];//临时数组存储临时排序值intnum;//计算统计逆序对数intN=2;//数据规模clock_tbegintimes,endtimes;//clock_t为clock()函数返回的变量类型doubleduration;//运行时间计算intheapsize;//堆长度//随机生成数函数intnumber(){inta;a=r

6、and()%10000+1;//随机生成1到一万之间的整数returna;}//初始化函数对数组a[]初始化。voidinit(){memset(temp,0,MAX*sizeof(int));//临时数组清零for(inti=0;i

7、&j<=right){//未超限进行循环填数if(a[i]>a[j]){//左边比右边大temp[n++]=a[j++];num+=mid-i+1;//从i到mid都比a[j]大}else{temp[n++]=a[i++];}}if(i>mid){//左边全部填满了，填右边while(j<=right){temp[n++]=a[j++];}}else{//右边填满，填左边while(i<=mid){temp[n++]=a[i++];}}for(intk=0;k<=length;k++){//最后临时数组赋值到原数组