實(shí)驗(yàn)4：遞歸與分治策略的應(yīng)用

課程實(shí)驗(yàn)報(bào)告課程名稱算法分析與設(shè)計(jì)班級實(shí)驗(yàn)日期姓名學(xué)號實(shí)驗(yàn)成績實(shí)驗(yàn)名稱實(shí)驗(yàn)4：遞歸與分治策略的應(yīng)用實(shí)驗(yàn)?zāi)康募耙笳莆辗种尾呗缘幕静襟E；掌握分治策略的思想。實(shí)驗(yàn)環(huán)境操作系統(tǒng)：WindowsIDE：VisualC++實(shí)驗(yàn)內(nèi)容（1） 排序算法分別實(shí)現(xiàn)歸并排序、快速排序和堆排序，輸入規(guī)模N=64,128,256,512,???（N取至單次排序運(yùn)行時(shí)間不超過3分鐘），輸入數(shù)據(jù)隨機(jī)生成1-10000之間的整數(shù)，記錄實(shí)驗(yàn)結(jié)果，做出運(yùn)行時(shí)間與輸入規(guī)模之間的關(guān)系曲線圖，說明算法的時(shí)間復(fù)雜度和空間復(fù)雜度，根據(jù)曲線圖比較3種排序算法的優(yōu)劣。（2） 矩陣乘法調(diào)研Strassen矩陣乘算法，隨機(jī)生成N*N的矩陣，矩陣中的每個(gè)數(shù)字為1-100之間的整數(shù)，N=4,8,16…（N取至單次矩陣乘時(shí)1可不超過3分鐘），分別用Strassen算法和你能想到的其它方法（例如直接計(jì)算）實(shí)現(xiàn)矩陣乘運(yùn)算，做出運(yùn)行時(shí)間與輸入規(guī)模之間的關(guān)系曲線圖，并簡要分析Strassen算法和你所實(shí)現(xiàn)的方法的時(shí)間復(fù)雜度。調(diào)試過程及實(shí)驗(yàn)運(yùn)行時(shí)截圖：并歸排序：

運(yùn)行到一定規(guī)模：70氣0耳1耳0^+0U0^+000^00^0 fO^+UUOiiUOOi*634865386598677868286838688869787098709884989248938894389558956899290289041904IO92149237925992639277927892899293931199415941794189433943794429443944794529479996459654966096619677967996819686972497900992599259937996199679989此次用時(shí)為1毫秒進(jìn)行規(guī)模為2M8的排序原始數(shù)組為：199411322915164197245172975214218682647848463668218904972813289366640688620?58284519597382580750511387734340ClmC7OOOfiOlf匚從GM 1077AHTkkAACOCQ堆排序：HEtt=C;\Winco?\5ystBirn32\Gnnd進(jìn)廳規(guī)橈為4的排序原始數(shù)組為：2549335351686404排厚后數(shù)組為：2549335351686404此次用時(shí)為0毫秒進(jìn)行規(guī)模為8的排序原始數(shù)組為：25493353516864046497735645805331排序后額組為：25493353458051685331640464977356此次用時(shí)為0毫秒進(jìn)行規(guī)橈為2的排序原始數(shù)組為：25493353516864046497735645S0533173127排序后數(shù)組為：731254?272533534580516S522653316404此次用時(shí)需0亨秒運(yùn)行到一定規(guī)模：1 V5/J知fVb/yVbbbVba/VbbyVbVbV6U-663966496649664966596669667966796689969896989698969897059712971997219722629762976797699769977497759775977697980198039804980698119820982098219824398839888988898929895989799009903990940994499499950995999619964996799689此次用時(shí)為4毫秒進(jìn)行規(guī)模為8192的排序原始數(shù)組為：255620828128899543595209805560474298287933327320519367334555408AC\AQ1&AA111R血"7A1 只勺尺只 7^/10AAQQQ矩陣乘法：1樸素算法:

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

Q7Q.97A21C.375369276061969232442192ALT三種算法時(shí)間復(fù)雜度2000013000160001400012000100003000600040002000□橫坐標(biāo)計(jì)算規(guī)模：1：8129 2：655363：1310724：2621445：1048576隨著輸入規(guī)模的增大，通過三種算法的時(shí)間記錄做成折線圖觀察不難發(fā)現(xiàn)，在初期，三種算法所用時(shí)間幾乎相等，隨著輸入規(guī)模的不斷增大，堆排序和快速排序仍然能夠保持相對較小的增長，而并歸排序所用時(shí)間復(fù)雜度開始大幅度增加?？焖倥判蚬皇强?，數(shù)據(jù)越大優(yōu)勢越明顯，并且實(shí)現(xiàn)上也較為簡單。理論上它的平均時(shí)間和歸并排序，堆排序都是一樣的(在最壞情況還還不如它們)，都是0(nlog2n),但實(shí)際運(yùn)行來看比它們兩者的速度都快一倍以上。COOL！合并排序需要額外相同規(guī)模的數(shù)組，空間復(fù)雜度為0(n)。從具體實(shí)現(xiàn)來看，這只是一種理論上的優(yōu)秀算法，想法比較簡單直接，但實(shí)現(xiàn)上比quicksort復(fù)雜，運(yùn)行時(shí)間也差，在數(shù)據(jù)很大的時(shí)候運(yùn)行時(shí)間是heapsort的兩倍，更不用說quicksort

了。堆排序利用了二分樹的結(jié)構(gòu)，將時(shí)間復(fù)雜度降到0(nlog2n),理論上和實(shí)現(xiàn)上表現(xiàn)都不錯(cuò)，并且發(fā)現(xiàn)在數(shù)據(jù)量是10000000時(shí)，甚至優(yōu)于快排，可能是運(yùn)行時(shí)數(shù)據(jù)的問題。對于strassen算法對其時(shí)間復(fù)雜度分析：T(n)=7T(n/2)+0(n);而樸素算法的時(shí)間復(fù)雜度為n的三次方。600002 3 4 5500002 3 4 540000300002000010000□隨著數(shù)據(jù)增大，也出現(xiàn)乘方級別的時(shí)間復(fù)雜度差距。//頭文件#include〈iostream〉#include〈stdio.h〉#include〈windows.h〉#include〈time.h〉#include<string.h〉#definePARENT(i)(i/2) //幾個(gè)較簡單函數(shù)#defineLEFT(i)(2*i+1)#defineRIGHT(i)(2*i+2)usingnamespacestd;//定義所需要變量等#defineMAX100000inta[MAXinta[MAX];inttemp[MAX];intnum;intN=2;//臨時(shí)數(shù)組存儲臨時(shí)排序值//計(jì)算統(tǒng)計(jì)逆序?qū)?shù)//數(shù)據(jù)規(guī)模clock_tbegintimes,endtimes;//clock_t為clock()函數(shù)返回的變量類型doubleduration; //運(yùn)行時(shí)間計(jì)算intheapsize; //堆長度

//隨機(jī)生成數(shù)函數(shù)intnumber(){inta;a=rand()%10000+1; //隨機(jī)生成1到一萬之間的整數(shù)returna;}//初始化函數(shù)對數(shù)組a[]初始化。voidinit(){memset(temp,0,MAX*sizeof(int)); //臨時(shí)數(shù)組清零for(inti=0;i<N;i++){ //新數(shù)組賦值a[i]=number();}return;}//單次并歸挑選voidMerge(intleft,intmid,intright)//需要三個(gè)參數(shù)，將原來數(shù)組分割{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開始為左半部分//未超限進(jìn)行循環(huán)填數(shù)//左邊比右邊大//從i到mid都比a[j]大//左邊全部填滿了，填右邊//右邊填滿，填左邊//最后臨時(shí)數(shù)組賦值到原數(shù)組//遞歸進(jìn)行并歸排序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作為軸//這個(gè)i坐標(biāo)左邊的值是比a[right]小的//交換//最后把i+1和right交換，這樣軸就是i+1了必須是保證i+1上當(dāng)初就是作為標(biāo)桿的a[right]啊。returni+1;}//遞歸進(jìn)行快排整體voidQuickSort(intleft,intright){if(left〈right){intq=Partition(left,right);QuickSort(left,q-1);QuickSort(q+1,right);}}//堆排序，函數(shù)太多，新建一個(gè)命名空間namespaceMySort{template〈typenameT>//堆排序的大頂堆優(yōu)化(找數(shù))voidMax_Heapify(T*arr,inti,size_theapSiz){//從元素A[i]、A[LEFT(i)]、A[RIGHT(i)]中找出最大的，并將其下標(biāo)保存在Largest中//sizetheapSize=sizeof(arr)/sizeof(*(arr));也就是數(shù)量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為根的子樹已經(jīng)是最大堆}template〈typenameT> //建立大頂堆，采用上面大頂堆方法進(jìn)行優(yōu)化voidBuild_Max_Heap(T*arr,size_theapSize){ //從底部開始進(jìn)行向上優(yōu)化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;//依次增大計(jì)算規(guī)模srand((unsigned)time(NULL));//給一個(gè)時(shí)間種子init();//初始化一次cout〈〈"進(jìn)行規(guī)模為"〈〈N〈〈"的排序"〈〈endl;cout〈〈"原始數(shù)組為：〃；for(inti=0;i〈N;i++){cout〈〈a[i]〈〈"";}cout〈〈endl;begintimes=clock();//計(jì)時(shí)開始MergeSort(0,N-1);QuickSort(0,N-1);MySort::HeapSort〈int〉(a,N);endtimes=clock();//計(jì)時(shí)結(jié)束duration=1000*(double)(endtimes-begintimes)/CLK_TCK;//總共用時(shí)(毫秒)cout<<"排序后數(shù)組為：〃；for(inti=0;i<N;i++){cout〈〈a[i]<<"";}cout〈〈endl;cout<<"此次用時(shí)為"<<duration<<"毫秒"<<endl<<endl<<endl;//記錄實(shí)驗(yàn)結(jié)果，注意運(yùn)行一次手動進(jìn)行數(shù)據(jù)轉(zhuǎn)移，清除數(shù)據(jù)FILE*fpWrite1=fopen("data1.txt","a+");//記錄實(shí)驗(yàn)結(jié)果fprintf(fpWrite1,"%d\n",N);fclose(fpWrite1);FILE*fpWrite2=fopen("data2.txt","a+");//記錄實(shí)驗(yàn)結(jié)果fprintf(fpWrite2,"%d\n",duration);fclose(fpWrite2);}while(duration<180000);//單次時(shí)間小于3分鐘return0;}#include<iostream〉#include<stdio.h〉#include〈time.h〉#include〈windows.h〉#defineMAX10000usingnamespacestd;intN;clock_tbegintimes,endtimes;//clock_t為clock()函數(shù)返回的變量類型doubleduration; //運(yùn)行時(shí)間計(jì)算//隨機(jī)生成數(shù)函數(shù)intnumber(){inta;a=rand()%100+1; //隨機(jī)生成1到一萬之間的整數(shù)returna;}//最樸素算法三重循環(huán)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];

}//獲取矩陣//四塊矩陣的分別計(jì)算//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;}}//初始化函數(shù)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();}}}//輸出函數(shù)voidinput(int**arr,int**r,int