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

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

运行到一定规模：70气0耳1耳0^+0U0^+000^00^0 fO^+UUOiiUOOi*634865386598677868286838688869787098709884989248938894389558956899290289041904IO92149237925992639277927892899293931199415941794189433943794429443944794529479996459654966096619677967996819686972497900992599259937996199679989此次用时为1毫秒进行规模为2M8的排序原始数组为：199411322915164197245172975214218682647848463668218904972813289366640688620?58284519597382580750511387734340ClmC7OOOfiOlf匚从GM 1077AHTkkAACOCQ堆排序：HEtt=C;\Winco™\5ystBirn32\Gnnd进厅规橈为4的排序原始数组为：2549335351686404排厚后数组为：2549335351686404此次用时为0毫秒进行规模为8的排序原始数组为：25493353516864046497735645805331排序后额组为：25493353458051685331640464977356此次用时为0毫秒进行规橈为2的排序原始数组为：25493353516864046497735645S0533173127排序后数组为：731254?272533534580516S522653316404此次用时需0亨秒运行到一定规模：1 V5/J知fVb/yVbbbVba/VbbyVbVbV6U-663966496649664966596669667966796689969896989698969897059712971997219722629762976797699769977497759775977697980198039804980698119820982098219824398839888988898929895989799009903990940994499499950995999619964996799689此次用时为4毫秒进行规模为8192的排序原始数组为：255620828128899543595209805560474298287933327320519367334555408AC\AQ1&AA111R血"7A1 只勺尺只 7^/10AAQQQ矩阵乘法：1朴素算法:

圃 ndows\5ystern32\cmd.ese矩阵A78911269947B33.179878443774895矩阵Et636350991b&B658656821t9237188勺相乘后的矩阵G139128737158031996115145130031853919562(8704S91417302144531095592461739518630所用时间为；0矩阵A：7RQI1?AOon047口QQpoI344甘/I44YZZI I04ItSOIMBIZ2Q5I■1578441766931609131913171652561545231629751726961584051584391423991571701691591669791683491578971578771432761744031501581655;47168105164994172802162680151667162137166/，所用时间为：2:矩阵A8868362366647511002431624808941仁占86694569824644481009673070226778；751231368542320231996829854234:597357212315562298765739585784909320612396826923』b?17151QQ3960713?MR6?156R5295#2Strassen矩阵乘算法矩阵A7?18193B2816452101472B86577747矩阵R61002263929335317?6531236555756相乘后的矩阵03859128996973810012899732381003407697381001225876488100340776488576所用时间肉：0矩阵A7?IS1?3&28164524a电川-rne&止上-rrta-t一定规模后：297492159521595406002409230304303044324625289316243162438825所用时间为:矩阵A79181938599636496469769453650256346195&17533292MQO4837736504365043240225289316243162438825415703704137041294512528931624316243882536438336613366137034391543825338253317944157037041370412945139154382533825331794313023390733907504743825623082308822312325624822482533342938529522952128195610551o094134487294153439673978935o5^245438285126225167423694115H0495091724o879955376749^51198981469&6783229574283.^16453388C.

Q7Q.97A21C.375369276061969232442192ALT三种算法时间复杂度2000013000160001400012000100003000600040002000□横坐标计算规模：1：8129 2：655363：1310724：2621445：1048576随着输入规模的增大，通过三种算法的时间记录做成折线图观察不难发现，在初期，三种算法所用时间几乎相等，随着输入规模的不断增大，堆排序和快速排序仍然能够保持相对较小的增长，而并归排序所用时间复杂度开始大幅度增加。快速排序果然是快，数据越大优势越明显，并且实现上也较为简单。理论上它的平均时间和归并排序，堆排序都是一样的(在最坏情况还还不如它们)，都是0(nlog2n),但实际运行来看比它们两者的速度都快一倍以上。COOL！合并排序需要额外相同规模的数组，空间复杂度为0(n)。从具体实现来看，这只是一种理论上的优秀算法，想法比较简单直接，但实现上比quicksort复杂，运行时间也差，在数据很大的时候运行时间是heapsort的两倍，更不用说quicksort

了。堆排序利用了二分树的结构，将时间复杂度降到0(nlog2n),理论上和实现上表现都不错，并且发现在数据量是10000000时，甚至优于快排，可能是运行时数据的问题。对于strassen算法对其时间复杂度分析：T(n)=7T(n/2)+0(n);而朴素算法的时间复杂度为n的三次方。600002 3 4 5500002 3 4 540000300002000010000□随着数据增大，也出现乘方级别的时间复杂度差距。//头文件#include〈iostream〉#include〈stdio.h〉#include〈windows.h〉#include〈time.h〉#include<string.h〉#definePARENT(i)(i/2) //几个较简单函数#defineLEFT(i)(2*i+1)#defineRIGHT(i)(2*i+2)usingnamespacestd;//定义所需要变量等#defineMAX100000inta[MAXinta[MAX];inttemp[MAX];intnum;intN=2;//临时数组存储临时排序值//计算统计逆序对数//数据规模clock_tbegintimes,endtimes;//clock_t为clock()函数返回的变量类型doubleduration; //运行时间计算intheapsize; //堆长度

//随机生成数函数intnumber(){inta;a=rand()%10000+1; //随机生成1到一万之间的整数returna;}//初始化函数对数组a[]初始化。voidinit(){memset(temp,0,MAX*sizeof(int)); //临时数组清零for(inti=0;i<N;i++){ //新数组赋值a[i]=number();}return;}//单次并归挑选voidMerge(intleft,intmid,intright)//需要三个参数，将原来数组分割{inti=left,j=mid+1,n=0,最左边，j为右半部分最左边while(i<=mid&&j〈二right){if(a[i]〉a[j]){temp[n++]=a[j++];num+=mid—i+1;}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++){a[left+k]=temp[k];length=right—length=right—left;//i开始为左半部分//未超限进行循环填数//左边比右边大//从i到mid都比a[j]大//左边全部填满了，填右边//右边填满，填左边//最后临时数组赋值到原数组//递归进行并归排序voidMergeSort(intleft,intright){if(left〈right){intmid=(left+right)/2;MergeSort(left,mid);MergeSort(mid+1,right);Merge(left,mid,right);}}//快速排序一次intPartition(intleft,intright){inti=left-inti=left-1;for(intj=left;j〈二right-if(a[j]<a[right]){i++;swap(a[i],a[j]);}}swap(a[i+1],a[right]);1;j++){//把right作为轴//这个i坐标左边的值是比a[right]小的//交换//最后把i+1和right交换，这样轴就是i+1了必须是保证i+1上当初就是作为标杆的a[right]啊。returni+1;}//递归进行快排整体voidQuickSort(intleft,intright){if(left〈right){intq=Partition(left,right);QuickSort(left,q-1);QuickSort(q+1,right);}}//堆排序，函数太多，新建一个命名空间namespaceMySort{template〈typenameT>//堆排序的大顶堆优化(找数)voidMax_Heapify(T*arr,inti,size_theapSiz){//从元素A[i]、A[LEFT(i)]、A[RIGHT(i)]中找出最大的，并将其下标保存在Largest中//sizetheapSize=sizeof(arr)/sizeof(*(arr));也就是数量nintl=LEFT(i);intr=RIGHT(i);intlargest;//寻找if(l〈heapSize&&*(arr+l)>*(arr+i))largest=l;elselargest=i;if(r<heapSize&&*(arr+r)〉*(arr+largest))largest=r;if(largest!=i){swap(*(arr+i),*(arr+largest));Max_Heapify(arr,largest,heapSiz);}//如果A[i]是最大的，则以i为根的子树已经是最大堆}template〈typenameT> //建立大顶堆，采用上面大顶堆方法进行优化voidBuild_Max_Heap(T*arr,size_theapSize){ //从底部开始进行向上优化for(inti=heapSize/2-1;i>=0;i--)Max_Heapify(iri,i,heapSize);}template<typenameT> //获得最大顶堆，堆排序开始，即元素出堆voidHeapSort(T*ar:,size_theapSize){Build_Max_Heap(,rr,heapSize);for(inti=heapSize-1;i>0;i--){swap(*arr,*(arr+i));Max_Heapify(arr,0,i);}}}intmain(){N=2;do{N*=2;//依次增大计算规模srand((unsigned)time(NULL));//给一个时间种子init();//初始化一次cout〈〈"进行规模为"〈〈N〈〈"的排序"〈〈endl;cout〈〈"原始数组为：〃；for(inti=0;i〈N;i++){cout〈〈a[i]〈〈"";}cout〈〈endl;begintimes=clock();//计时开始MergeSort(0,N-1);QuickSort(0,N-1);MySort::HeapSort〈int〉(a,N);endtimes=clock();//计时结束duration=1000*(double)(endtimes-begintimes)/CLK_TCK;//总共用时(毫秒)cout<<"排序后数组为：〃；for(inti=0;i<N;i++){cout〈〈a[i]<<"";}cout〈〈endl;cout<<"此次用时为"<<duration<<"毫秒"<<endl<<endl<<endl;//记录实验结果，注意运行一次手动进行数据转移，清除数据FILE*fpWrite1=fopen("data1.txt","a+");//记录实验结果fprintf(fpWrite1,"%d\n",N);fclose(fpWrite1);FILE*fpWrite2=fopen("data2.txt","a+");//记录实验结果fprintf(fpWrite2,"%d\n",duration);fclose(fpWrite2);}while(duration<180000);//单次时间小于3分钟return0;}#include<iostream〉#include<stdio.h〉#include〈time.h〉#include〈windows.h〉#defineMAX10000usingnamespacestd;intN;clock_tbegintimes,endtimes;//clock_t为clock()函数返回的变量类型doubleduration; //运行时间计算//随机生成数函数intnumber(){inta;a=rand()%100+1; //随机生成1到一万之间的整数returna;}//最朴素算法三重循环voidpusu(int**arr,int**brr,int**crr){for(inti=0;i〈二N-1;i++){for(intj=0;j<=N-1;j++){for(intk=0;k<=N-1;k++){

err +=arr[i][k]*brr[k][j];}}}}//Strassen矩阵乘法算法，矩阵分块，仅仅针对2的n次幕次阶处理voidgerResultStrassen(int**arr,int**rr,inti,int**err){if(n==1){err[0][0]+=arr[0][0]*brr[0][0];}else{intm=n/2;int **arr11 = new int*[m];int **arr12 = new int*[m];int **arr21 = new int*[m];int **arr22 = new int*[m];int **brr11 = new int*[m];int **brr12 = new int*[m];int **brr21 = new int*[m];int **brr22 = new int*[m];int **err11 = new int*[m];int **err12 = new int*[m];int **err21 = new int*[m];int **err22 = new int*[m];for(inti=0;i<m;++i){arr11[i]=newint[m];arr12[i]=newint[m];arr21[i]=newint[m];arr22[i]=newint[m];brr11[i]=newint[m];brr12[i]=newint[m];brr21[i]=newint[m];brr22[i]=newint[m];err11[i]=newint[m];err12[i]=newint[m];err21[i]=newint[m];err22[i]=newint[m];

}//获取矩阵//四块矩阵的分别计算//11for(inti=0;i<m;++i){for(intj=0;j<m;++j){arr11[i][j]=arr[i][j];brr11[i][j]=brr[i][j];}}//22for(inti=m;i<n;++i){for(intj=m;j<n;++j){arr22[i-m][j-m]=arr[i][j];brr22[i-m][j-m]=brr[i][j];}}//12for(inti=0;i<m;++i){for(intj=m;j<n;++j){arr12[i][j-m]=arr[i][j];brr12[i][j-m]=brr[i][j];}}//21for(inti=m;i<n;++i){for(intj=0;j<m;++j){arr21[i-m][j]=arr[i][j];brr21[i-m][j]=brr[i][j];}}for(inti=0;i<m;++i){for(intj=0;j<m;++j){crr11[i][j]=0;crr12[i][j]=0;crr21[i][j]=0;crr22[i][j]=0;}}//递归分治gerResultStrassen(arr11,brr11,m,crr11);gerResultStrassen(arr12,brr21,m,crr11);gerResultStrassen(arr11,brr12,m,err⑵；

gerResultStrassen(arr12,brr22,m,err⑵；gerResultStrassen(arr21,brr11,m,err21);gerResultStrassen(arr22,brr21,m,err21);gerResultStrassen(arr21,brr12,m,err22);gerResultStrassen(arr22,brr22,m,err22);//一下是矩阵的分为四块//11for(inti=0;i<m;++i){for(intj=0;j<m;++j){err[i][j]+=crr11[i][j];}}//22for(inti=m;i<n;++i){for(intj=m;j<n;++j){err[i][j]+=err22[i-m][j-m];}}//12for(inti=0;i<m;++i){for(intj=m;j<n;++j){crr[i][j]+=err12[i][j-m];}}//21for(inti=m;i<n;++i){for(intj=0;j<m;++j){crr[i][j]+=err12[i-m][j];}}//后期处理for(inti=0;i<m;++i){delete[]arr11[i];delete[]brr11[i];delete[]err11[i];delete]]arr12[i];delete[]brr12[i];delete[]err12[i];delete]]arr21[i];

delete[]brr21[i];delete[]crr21[i];delete]]arr22[i];delete[]brr22[i];delete]]crr22[i];}delete]]arr11;delete]]brr11;delete]]crr11;delete]]arr12;delete]]brr12;delete]]crr12;delete]]arr21;delete]]brr21;delete]]crr21;delete]]arr22;delete]]brr22;delete]]crr22;}}//初始化函数voidinit(int**ar:,int**rr,int**：rr){//初始化赋值for(inti=0;i<N;++i){for(intj=0;j<N;++j){arr]i]]j]=number();crr]i]]j]=0;}}for(inti=0;i<N;++i){for(intj=0;j<N;++j){brr]i]]j]=number();}}}//输出函数voidinput(int**arr,int**r,int