算法的時間復(fù)雜度實驗報告

1、.實驗一算法的時間復(fù)雜度一、實驗?zāi)康呐c要求熟悉 C/C+ 語言的集成開發(fā)環(huán)境；通過本實驗加深對算法分析基礎(chǔ)知識的理解。軟件環(huán)境：操作系統(tǒng)： windows7旗艦版集成開發(fā)環(huán)境：visual studio 2010旗艦版硬件環(huán)境：處理器：因特爾Core i3 M 380內(nèi)存：2GB二、實驗內(nèi)容 :掌握算法分析的基本方法，并結(jié)合具體的問題深入認(rèn)識算法的時間復(fù)雜度分析。三、實驗題定義一個足夠大的整型數(shù)組，并分別用起泡排序、簡單選擇排序、 快速排序和歸并排序?qū)?shù)組中的數(shù)據(jù)進(jìn)行排序（按從小到大的順序排序），記錄每種算法的實際耗時，并結(jié)合數(shù)據(jù)結(jié)構(gòu)中的知識對算法的時間復(fù)雜度分析進(jìn)行說明。實驗數(shù)據(jù)分兩種情況：

2、1、數(shù)組中的數(shù)據(jù)隨機生成；2、數(shù)組中的數(shù)據(jù)已經(jīng)是非遞減有序。四、實驗步驟理解算法思想和問題要求；編程實現(xiàn)題目要求；上機輸入和調(diào)試自己所編的程序；驗證分析實驗結(jié)果；整理出實驗報告。'.五、實驗程序#include<Windows.h>#include<stdio.h>#include<iostream>#include<time.h>/導(dǎo)入時間庫函數(shù)文件using namespace std;void BubbleSort(int arr,int n);void QuickSort(int arr,int left,int right);v

3、oid SelectSort(int arr,int n);void UnionSort(int arr,int left,int right);int Partition(int arr,int left,int right);void Union(int arr,int left,int mid,int right);const int ARRAY_MAXSIZE=10000;/定義數(shù)組最大長度int main(int argc,char *argv)/測試調(diào)用的排序算法耗時int array_SortARRAY_MAXSIZE;/聲明待排序的數(shù)組int array_Sort2ARRAY_

4、MAXSIZE;for(int i=0;i<=ARRAY_MAXSIZE;i+)/生成隨機數(shù)組，大小為10000array_Sorti=rand()%500;for(int j=0;j<ARRAY_MAXSIZE;j+)/生成非遞減數(shù)組，大小均為10000array_Sort2j=j;clock_t start,end;/聲明開始和結(jié)束的時間計數(shù)器start=clock();/排序開始時間計數(shù)器BubbleSort(array_Sort,ARRAY_MAXSIZE);/起泡排序算法測試end=clock();/排序結(jié)束時間計數(shù)器cout<<" 隨機數(shù)組起泡排序

5、測試耗時為："cout<<(double)(end-start)<<" ms"<<endl;start=clock();QuickSort(array_Sort,0,ARRAY_MAXSIZE-1); / 快速排序算法測試 end=clock();cout<<" 隨機數(shù)組快速排序測試耗時為："cout<<(double)(end-start)<<" ms"<<endl;start=clock();SelectSort(array_Sort,A

6、RRAY_MAXSIZE); / 選擇排序算法測試 end=clock();cout<<" 隨機數(shù)組選擇排序測試耗時為："cout<<(double)(end-start)<<" ms"<<endl;start=clock();UnionSort(array_Sort,0,ARRAY_MAXSIZE-1);/歸并排序算法測試'.end=clock();cout<<" 隨機數(shù)組歸并排序測試耗時為："cout<<(double)(end-start)<&

7、lt;" ms"<<endl;cout<<endl;start=clock();BubbleSort(array_Sort,ARRAY_MAXSIZE);end=clock();cout<<" 非遞減數(shù)組起泡排序測試耗時為："cout<<(double)(end-start)<<" ms"<<endl;start=clock();QuickSort(array_Sort,0,ARRAY_MAXSIZE-1);end=clock();cout<<&quo

8、t; 非遞減數(shù)組快速排序測試耗時為："cout<<(double)(end-start)<<" ms"<<endl;start=clock();SelectSort(array_Sort,ARRAY_MAXSIZE);end=clock();cout<<" 非遞減數(shù)組用選擇排序測試耗時為："cout<<(double)(end-start)<<" ms"<<endl;start=clock();UnionSort(array_Sort,0,A

9、RRAY_MAXSIZE-1);end=clock();cout<<" 非遞減數(shù)組用歸并排序測試耗時為："cout<<(double)(end-start)<<" ms"<<endl;system("pause");return 0;/ 起泡排序的定義，需要兩個參數(shù)待排數(shù)組和數(shù)組長度void BubbleSort(int arr,int n)int exchange=n;/記錄本次交換的位置int bound=0;/每次待排序的到的位置int temp=0;/臨時變量存儲交換時的一個值w

10、hile(exchange)bound=exchange;exchange=0;for(int i=0;i<bound;i+)if(arri>arri+1)/判斷最近兩個并做交換temp=arri;'.arri=arri+1;arri+1=temp;exchange=i;/for循環(huán)結(jié)束時記錄的是本趟循環(huán)最后交換的位置/ 快速排序的定義，需要三個參數(shù)待排序數(shù)組、數(shù)組左邊界和右邊界void QuickSort(int arr,int left,int right)if(left<right)/遞歸結(jié)束int pivot=Partition(arr,left,right)

11、;/進(jìn)行一次劃分QuickSort(arr,left,pivot-1);/遞歸對劃分后的左側(cè)快速排序QuickSort(arr,pivot+1,right);/遞歸對劃分后的又側(cè)快速排序/ 選擇排序的定義，需要兩個參數(shù)待排序數(shù)組和數(shù)組長度void SelectSort(int arr ,int n)int index=0;/記錄每次比較中的較小數(shù)的位置int temp=0;/交換時的臨時變量for(int i=0;i<n;i+)index=i;/默認(rèn)每次循環(huán)時第一個為最小for(int j=i+1;j<=n;j+)if(arrj<arrindex)index=j;if(ind

12、ex!=i)/如果當(dāng)前的最小值不是arri,則和記錄位置的值交換temp=arri;arri=arrindex;arrindex=temp;/ 歸并排序的定義，需要三個參數(shù)待排序數(shù)組、數(shù)組左邊界和右邊界void UnionSort(int arr,int left,int right)if(left<right)/序列長度超過一，則進(jìn)行自序列的劃分int mid=(left+right)/2;/將待排序列劃分為兩部分UnionSort(arr,left,mid);/對左序列進(jìn)行歸并UnionSort(arr,mid+1,right); /對又序列進(jìn)行歸并Union(arr,left,mi

13、d,right);/將兩個有序序列合并成一個有序的序列'./ 一次快速排序int Partition(int arr,int left,int right )int i=left;/作為劃分中的樞紐值int j=right;/右邊界int temp=0;/交換時的臨時變量dodo i+;/掃描左側(cè)，當(dāng)當(dāng)前位置值大于樞紐值時停止while (arri<arrleft);do j-;/掃描右側(cè)，當(dāng)當(dāng)前位置值大于樞紐值時停止while (arrj>arrleft);if(i<j)temp=arri;/交換當(dāng)前 i 和 j 記錄位置的值arri=arrj;arrj=temp;

14、while(i<j) ;/當(dāng)i<j 時繼續(xù) dotemp=arrleft;/i>j時本趟循環(huán)結(jié)束，交換樞紐值和j 位置的值arrleft=arrj;arrj=temp;return j;/ 歸并排序合并兩有序的子序列void Union(int arr,int left,int mid,int right)int temp10000;/臨時使用的輔助數(shù)組int i=left;int j=mid+1;int k=0;while(i<=mid)&&(j<=right)/比較后把 i ， j 中最小的放入temp 中if(arri<=arrj)te

15、mpk+=arri+;else tempk+=arrj+;while(i<=mid)tempk+=arri+;while(j<=right)tempk+=arrj+;for(i=0,k=left;k<=right; )arrk+=tempi+;/把排好序臨時數(shù)組放回原數(shù)組'.六、實驗結(jié)果1.數(shù)組大小 ARRAY_MAXSIZE為 10000 如下：2.數(shù)組大小 ARRAY_MAXSIZE為 8000 如下3.數(shù)組大小 ARRAY_MAXSIZE為 5000 如下：七、實驗分析1、各算法時間時間消耗圖'.2、各算法時間性能分析表：方法最好情況最壞情況平均情況起泡排序O(n)O(n)O(n)快速排序O(nlog2n)O(n)O(nlog2n)選擇排序O(n)O(n)O(n)歸并排序O(nlog2n)O(nlog2n)O(nlog2n)3、分析與說明：由算法時間復(fù)雜度表分析，起泡排序在最好情況下時間性能好，最壞情況和平均情況和選擇排序一樣，選擇排序的時間性能都不高，均為 O(n )，根據(jù)平均情況來看， 快速排序和歸并排序的時間性能一樣，且最壞情況時歸并排序優(yōu)于快速排序。對于隨機數(shù)組序列，數(shù)組大小為10000，8000，5