實(shí)驗(yàn)一--算法的時(shí)間復(fù)雜度

1、實(shí)驗(yàn)一 算法的時(shí)間復(fù)雜度一、實(shí)驗(yàn)?zāi)康呐c要求熟悉C/C+語(yǔ)言的集成開發(fā)環(huán)境；通過本實(shí)驗(yàn)加深對(duì)算法分析基礎(chǔ)知識(shí)的理解。二、實(shí)驗(yàn)內(nèi)容：掌握算法分析的基本方法，并結(jié)合具體的問題深入認(rèn)識(shí)算法的時(shí)間復(fù)雜度分析。三、實(shí)驗(yàn)題定義一個(gè)足夠大的整型數(shù)組，并分別用起泡排序、簡(jiǎn)單選擇排序、快速排序和歸并排序 對(duì)數(shù)組中的數(shù)據(jù)進(jìn)行排序（按從小到大的順序排序），記錄每種算法的實(shí)際耗時(shí)，并結(jié)合數(shù) 據(jù)結(jié)構(gòu)中的知識(shí)對(duì)算法的時(shí)間復(fù)雜度分析進(jìn)行說明。實(shí)驗(yàn)數(shù)據(jù)分兩種情況：1、數(shù)組中的數(shù)據(jù)隨機(jī)生成；2、數(shù)組中的數(shù)據(jù)已經(jīng)是非遞減有序。四、實(shí)驗(yàn)步驟理解算法思想和問題要求；編程實(shí)現(xiàn)題目要求；上機(jī)輸入和調(diào)試自己所編的程序；驗(yàn)證分析實(shí)驗(yàn)結(jié)果；整理

2、出實(shí)驗(yàn)報(bào)告。五、實(shí)驗(yàn)程序#include #include using namespace std;const int n=5000; /可根據(jù)需要更改數(shù)組大小class Sortpublic:void Radom(); /生成一個(gè)隨機(jī)數(shù)數(shù)組void Order();/生成一個(gè)非遞減數(shù)組void BubbleSort(int r,int n);/ 冒泡排序void SelectSort(int r,int n);/簡(jiǎn)單選擇排序int Partition(int r,int first,int end);/快 速排序一次劃分算法void QuickSort(int r,int first,int

3、 end);/快 速排序void Merge(int r,int r1,int s,int m,int t);/一 次歸并排序void MergeSort(int r,int r1,int s,int t);/歸并排序int an;/存放隨機(jī)數(shù)的數(shù)組int a1n;/存放非遞減數(shù)據(jù)的數(shù)組int exchange;/冒泡排序中記載每次記錄交換的位置int bound;/冒泡排序中記錄無(wú)序區(qū)的最后一個(gè)記錄int index;/簡(jiǎn)單選擇排序中記錄在一趟比較過程中關(guān)鍵碼最小的記錄位置int pivot;/快速排序中的基準(zhǔn)記錄int temp;/用于排序中的交換;/=生 成隨機(jī)數(shù)組=void Sort:

4、Radom()/srand(unsigned(time(NULL);for(int i=0;in;i+)ai=rand()%800;/產(chǎn)生隨機(jī)數(shù)=/=生 成非遞減數(shù)組= void Sort:Order()for(int i=0;in;i+)a1i=i;/=/=冒泡排序=void Sort:BubbleSort(int r,int n)exchange=n-1; /第一趟冒泡排序的范圍是r0到rnwhile(exchange)bound=exchange;exchange=0;for(int j=0;jrj+1)temp=rj+1;rj+1=rj;rj=temp;exchange=j;=/=簡(jiǎn)單

5、選擇排序= void Sort:SelectSort(int r,int n) for(int i=0;in;i+)index=i;for(int j=i+1;j=n;j+)if(rjrindex)index=j;if(index!=i)( temp=ri;ri=rindex;rindex=temp;=/=!快速排序一次劃分算法=int Sort:Partition(int r,int first,int end)int i=first;int j=end;while(ij)while(ij&ri=rj-1) j-; /佑側(cè)掃描if(ij)temp=ri;ri=rj;rj=temp; /將較小

6、記錄換到前面i+;while(ij&ri=rj-1) i+; /左側(cè)掃描if(ij)temp=ri;ri=rj;rj=temp; /將較大記錄換到后面j-;return i; /i為軸值記錄的最終位置=/=三1快 速排序= void Sort:QuickSort(int r,int first,int end)if(firstend)pivot=Partition(r,first,end); 一次劃分QuickSort(r,first,pivot-1); /遞歸地對(duì)左側(cè)子序列進(jìn)行快速排序QuickSort(r,pivot+1,end); /遞歸地對(duì)右側(cè)子序列進(jìn)行快速排序=/=一 次歸并排序=v

7、oid Sort:Merge(int r,int r1,int s,int m,int t)int i=s;int j=m+1;int k=s;while(iv=m&jv=t)if(riv=rj)r1k+=ri+;else r1k+=rj+;if(iv=m) while(iv=m) /若第一個(gè)子序列沒處理完，則進(jìn)行收尾處理r1k+=ri+;else while(jv=t) /若第二個(gè)子序列沒處理完，則進(jìn)行收尾處理r1k+=rj+;/=/=歸并排序(遞歸)=void Sort:MergeSort(int r,int r1,int s,int t)if(s=t) r1s=rs;elseint m=

8、(s+t)/2;MergeSort(r,r1,s,m); 歸并排序前半個(gè)子序列MergeSort(r,r1,m+1,t); 歸并排序前半個(gè)子序列Merge(r1,r,s,m,t); /將兩個(gè)已排序的子序列歸并=/=主 函數(shù)= int main()Sort s;clock_t start,end;s.Radom();start=clock();s.BubbleSort(s.a,n);end=clock();cout隨機(jī)數(shù)組冒泡排序所需時(shí)間為：(double)(end-start)msendl;s.Radom();start=clock();s.SelectSort(s.a,n);end=cloc

9、k();cout隨機(jī)數(shù)組簡(jiǎn)單選擇排序所需時(shí)間為：(double)(end-start)msendl;s.Radom();start=clock();s.QuickSort(s.a,0,n-1);end=clock();cout隨機(jī)數(shù)組快速排序所需時(shí)間為：”(double)(end-start)”ms”endl;s.Radom();int bn=0;start=clock();s.MergeSort(s.a,b,0,n-1);end=clock();cout隨機(jī)數(shù)組歸并排序所需時(shí)間為：”(double)(end-start)”ms”endl;coutendl;start=clock();s.Bu

10、bbleSort(s.a1,n);end=clock();cout非遞減數(shù)組冒泡排序所需時(shí)間為：(double)(end-start)msendl;s.Radom();start=clock();s.SelectSort(s.a1,n);end=clock();cout非遞減數(shù)組簡(jiǎn)單選擇排序所需時(shí)間為：(double)(end-start)msendl;start=clock();s.QuickSort(s.a1,0,n-1);end=clock();cout非遞減數(shù)組快速排序所需時(shí)間為：”(double)(end-start)”ms”endl;start=clock();s.MergeSor

11、t(s.a1,b,0,n-1);end=clock();cout非遞減數(shù)組歸并排序所需時(shí)間為：”(double)(end-start)”ms” - - Jpn - j-l弓j-l弓j-l弓j-l弓y n ae Enu 壬而皇w而ti ffsffff c 一二 - 一二一二.o 申冊(cè)切申t 泡盤并y B1筒e;Kes 2: s s0 0 間:丸町丸丸數(shù)數(shù)數(shù)s當(dāng) n=11000 時(shí):s m 為011115 間: 阿丸丸9 廛W而所 JT擇rrrj rrrj mj mj rv- - Fv-卜：M-卜：M- 數(shù)數(shù)數(shù)當(dāng) n=13000 時(shí):實(shí)驗(yàn)結(jié)果制表:11-201 第二學(xué)期1算法設(shè)計(jì)與始析DebugU

12、ntitl: m s5 m9 1 0 間羽町丸丸需廛w而JT擇隨機(jī)數(shù)組n=1000n=3000n=5000n=7000n=9000n=11000冒泡排序1662141281453656簡(jiǎn)單選擇排序03162109203282快速排序0001600歸并排序0000015非遞減數(shù)組排序所花時(shí)間非遞減數(shù)組n=1000n=3000n=5000n=7000n=9000n=11000冒泡排序000000簡(jiǎn)單選擇排序01646110188282快速排序0314794172歸并排序000015隨機(jī)數(shù)組排序所需時(shí)間n15 0n=13000 0 407隨機(jī)數(shù)組時(shí)間復(fù)雜度函數(shù)曲線:隨機(jī)數(shù)組

13、( 間 時(shí)n=1000 n=3000 n=5000 n=7000 n=9000 n=11000 n=13000 數(shù)組大小冒泡排序 簡(jiǎn)單選擇排序 快速排序歸并排序非遞減數(shù)組時(shí)間復(fù)雜度函數(shù)曲線:非遞減數(shù)組數(shù)組大小一冒泡排序-簡(jiǎn)單選擇排序+快速排序歸并排序s( 間 時(shí)七、實(shí)驗(yàn)分析運(yùn)行環(huán)境：Visual C+ 6.0CPU： 2.53GHz 內(nèi)存：1.92GB系統(tǒng)：Microsoft Windows XP Professional 版本 2002冒泡排序：在最好情況下，待排序記錄序列為正序，算法只執(zhí)行一趟，進(jìn)行了 n-1次關(guān)鍵碼的比較，不需要移動(dòng)記錄，時(shí)間復(fù)雜度為O(n)；在最壞情況下，待排序記錄序列

14、為反序，每趟排序在無(wú)序序列中只有一個(gè)最大的記錄 被交換到最終位置，故算法執(zhí)行n-1趟，第i (1Win)趟排序執(zhí)行了 n-i次關(guān)鍵碼的比較 和n-i次記錄的交換，這樣，關(guān)鍵碼的比較次數(shù)為工(n-i) =n (n-1) /2，記錄的移動(dòng)次數(shù) 為3n (n-1) /2，因此，時(shí)間復(fù)雜度為O(n*n)；在平均情況下，冒泡排序的時(shí)間復(fù)雜度與最壞情況同數(shù)量級(jí)。冒泡排序是一種穩(wěn)定的排序方法。簡(jiǎn)單選擇排序：在選擇排序中記錄的移動(dòng)次數(shù)較少。在待排序列為正序時(shí)，記錄的移動(dòng)次數(shù)最少，為 0;第i趟排序需進(jìn)行n-i次比較，而選擇排序需進(jìn)行n-1趟排序，總比較次數(shù)為：E (n-1)= n(n-1)/2=O(n*n)所

15、以，總的時(shí)間復(fù)雜度為O(n*n),這是簡(jiǎn)單選擇排序最好、最壞、和平均的時(shí)間性能。簡(jiǎn)單選擇排序是一種穩(wěn)定的排序方法?？焖倥判颍涸谧詈们闆r下，每次劃分對(duì)一個(gè)記錄定位后，該記錄的左側(cè)子序列與右側(cè)子序列的長(zhǎng) 度相同。在具有n個(gè)記錄的序列中，對(duì)一個(gè)記錄定位要對(duì)整個(gè)待劃分序列掃描一遍，則所需 時(shí)間為O(n)。設(shè)T(n)是對(duì)n個(gè)記錄的序列進(jìn)行排序的時(shí)間，每次劃分后，把待劃分區(qū)間劃 分為長(zhǎng)度相等的兩個(gè)子序列，則有：T(n)W2T(n/2)+nW 2(2T(n/4)+n/2)+n=4T(n/4)+2nW4(2T(n/8+n/4)+2n=8T(n/8)+3nW nT(1)+nlogn=O(nlogn)因此，時(shí)間復(fù)雜度為O(nlogn)。在最壞情況下，待排序記錄序列正序或逆序，每次劃分只得到一個(gè)比上一次劃分少一 個(gè)記錄的子序列(另一個(gè)子序列為空)。此時(shí)，必須經(jīng)過n-1次遞歸調(diào)用才能把所有記錄定 位，而且第i趟劃分需要經(jīng)過n-i次關(guān)鍵碼的比較才能找到第i個(gè)記錄的基準(zhǔn)位置，因此， 總的比較次數(shù)為：E(n-i) =n (n-1) /2=O(n*n)記錄的移動(dòng)次數(shù)小于等于比較次數(shù)。因此，時(shí)間復(fù)雜度為O(n*n)。在平均情況下，設(shè)基準(zhǔn)記錄的關(guān)鍵碼第