算法時間復(fù)雜度

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

2、驗證分析實驗結(jié)果； 整理出實驗報告。五、實驗程序 #include<iostream> #include<time.h> #include<windows.h> using namespace std;void SelectSort(int r , int n)int i;int j;int index;int temp;for (i=0; i<n -1; i+)index=i;for (j=i+1; j<n; j+)if (rj<rindex) index=j;if (index!=i)temp=ri; ri=rindex; rindex

3、=temp;for(i=0;i<n;i+)cout<<ri<<" " cout<<"n"void BubbleSort(int r, int n)int temp;int exchange;int bound;exchange=n-1;while (exchange)bound=exchange; exchange=0;for (int j=0; j<bound; j+) if (rj>rj+1)temp=rj;rj=rj+1;rj+1=temp;exchange=j;for(int i=0;i<

4、;n;i+) cout<<ri<<" "cout<<"n"int Partition(int r, int first, int end)int i=first;int j=end;int temp;while (i<j)while (i<j && ri<= rj)j-;if (i<j)temp=ri;ri=rj; rj=temp;i+;while (i<j && ri<= rj) i+; if (i<j) temp=rj; rj=ri; ri=

5、temp;j-;return i;/ 快速排序void QuickSort(int r, int first, int end) if (first<end)int pivot=Partition(r, first, end);QuickSort(r, first, pivot -1);QuickSort(r, pivot+1, end);void Merge(int r, int r1, int s, int m, int t) int i=s;int j=m+1;int k=s;while (i<=m && j<=t)if (ri<=rj)r1k+=

6、ri+;elser1k+=rj+;if (i<=m)while (i<=m)r1k+=ri+;elsewhile (j<=t)r1k+=rj+;void MergePass(int r , int r1 , int n, int h)int i=0;int k;while (i<=n -2*h)Merge(r, r1, i, i+h -1, i+2*h -1); i+=2*h;if (i<n -h)Merge(r, r1, i, i+h -1, n);else for (k=i; k<=n; k+)r1k=rk;void MergeSort2(int r,

7、int r1, int r2,int s, int t) int m;if (s=t)r1s=rs;elsem=(s+t)/2;MergeSort2(r, r2, r1, s, m);MergeSort2(r, r2, r1, m+1, t); Merge(r2, r1, s, m, t);int main()int b100;const int numv=100; clock_t t=clock();for(int k=0;k<100;k+) bk=rand()%100;cout<<bk<<" "cout << "n 起

8、泡排序結(jié)果為： " << "n"BubbleSort(b, numv);cout<<clock() -t<<"ms"<<endl;cout<<"n 簡單選擇排序結(jié)果為： "<<"n"SelectSort(b, numv);cout<<clock() -t<<"ms"<<endl; cout<<"n 快速排序結(jié)果為： "<<"n

9、" QuickSort(b,0,100);for(int j=0;j<100;j+) cout<<bj<<" "cout<<"n"cout<<clock() -t<<"ms"<<endl;const int h=100;int b1h;for(int i=0;i<h;i+) b1i=rand()%k;int a1h;int c1h;cout<<"n 歸并排序結(jié)果為： "<<"n" MergeSort2(b1,a1,c1,0,h -1);for(int m=0; m < h; m+) cout<<a1m<<" "cout<<"n"cout<<(clock() -t)<<"ms"<<endl;return 0;六 實驗結(jié)果 當(dāng)隨機(jī)數(shù)為 10 時： 起泡排序結(jié)果為： 4ms 簡單選擇排序結(jié)果為： 7ms 快速排序結(jié)果為： 12ms 歸并排序結(jié)果為： 16ms 當(dāng)隨機(jī)數(shù)為 100 時： 起泡