实验一--算法的时间复杂度

1、实验一 算法的时间复杂度一、实验目的与要求熟悉C/C+语言的集成开发环境；通过本实验加深对算法分析基础知识的理解。二、实验内容：掌握算法分析的基本方法，并结合具体的问题深入认识算法的时间复杂度分析。三、实验题定义一个足够大的整型数组，并分别用起泡排序、简单选择排序、快速排序和归并排序 对数组中的数据进行排序（按从小到大的顺序排序），记录每种算法的实际耗时，并结合数 据结构中的知识对算法的时间复杂度分析进行说明。实验数据分两种情况：1、数组中的数据随机生成；2、数组中的数据已经是非递减有序。四、实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理

2、出实验报告。五、实验程序#include #include using namespace std;const int n=5000; /可根据需要更改数组大小class Sortpublic:void Radom(); /生成一个随机数数组void Order();/生成一个非递减数组void BubbleSort(int r,int n);/ 冒泡排序void SelectSort(int r,int 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;/存放随机数的数组int a1n;/存放非递减数据的数组int exchange;/冒泡排序中记载每次记录交换的位置int bound;/冒泡排序中记录无序区的最后一个记录int index;/简单选择排序中记录在一趟比较过程中关键码最小的记录位置int pivot;/快速排序中的基准记录int temp;/用于排序中的交换;/=生 成随机数组=void Sort:

4、Radom()/srand(unsigned(time(NULL);for(int i=0;in;i+)ai=rand()%800;/产生随机数=/=生 成非递减数组= 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;=/=简单

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-; /佑侧扫描if(ij)temp=ri;ri=rj;rj=temp; /将较小

6、记录换到前面i+;while(ij&ri=rj-1) i+; /左侧扫描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); /递归地对左侧子序列进行快速排序QuickSort(r,pivot+1,end); /递归地对右侧子序列进行快速排序=/=一 次归并排序=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) /若第一个子序列没处理完，则进行收尾处理r1k+=ri+;else while(jv=t) /若第二个子序列没处理完，则进行收尾处理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); 归并排序前半个子序列MergeSort(r,r1,m+1,t); 归并排序前半个子序列Merge(r1,r,s,m,t); /将两个已排序的子序列归并=/=主 函数= int main()Sort s;clock_t start,end;s.Radom();start=clock();s.BubbleSort(s.a,n);end=clock();cout随机数组冒泡排序所需时间为：(double)(end-start)msendl;s.Radom();start=clock();s.SelectSort(s.a,n);end=cloc

9、k();cout随机数组简单选择排序所需时间为：(double)(end-start)msendl;s.Radom();start=clock();s.QuickSort(s.a,0,n-1);end=clock();cout随机数组快速排序所需时间为：”(double)(end-start)”ms”endl;s.Radom();int bn=0;start=clock();s.MergeSort(s.a,b,0,n-1);end=clock();cout随机数组归并排序所需时间为：”(double)(end-start)”ms”endl;coutendl;start=clock();s.Bu

10、bbleSort(s.a1,n);end=clock();cout非递减数组冒泡排序所需时间为：(double)(end-start)msendl;s.Radom();start=clock();s.SelectSort(s.a1,n);end=clock();cout非递减数组简单选择排序所需时间为：(double)(end-start)msendl;start=clock();s.QuickSort(s.a1,0,n-1);end=clock();cout非递减数组快速排序所需时间为：”(double)(end-start)”ms”endl;start=clock();s.MergeSor

11、t(s.a1,b,0,n-1);end=clock();cout非递减数组归并排序所需时间为：”(double)(end-start)”ms” - - Jpn - j-l弓j-l弓j-l弓j-l弓y n ae Enu 壬而皇w而ti ffsffff c 一二 - 一二一二.o 申册切申t 泡盘并y B1筒e;Kes 2: s s0 0 间:丸町丸丸数数数s当 n=11000 时:s m 为011115 间: 阿丸丸9 廛W而所 JT择rrrj rrrj mj mj rv- - Fv-卜：M-卜：M- 数数数当 n=13000 时:实验结果制表:11-201 第二学期1算法设计与始析DebugU

12、ntitl: m s5 m9 1 0 间羽町丸丸需廛w而JT择随机数组n=1000n=3000n=5000n=7000n=9000n=11000冒泡排序1662141281453656简单选择排序03162109203282快速排序0001600归并排序0000015非递减数组排序所花时间非递减数组n=1000n=3000n=5000n=7000n=9000n=11000冒泡排序000000简单选择排序01646110188282快速排序0314794172归并排序000015随机数组排序所需时间n15 0n=13000 0 407随机数组时间复杂度函数曲线:随机数组

13、( 间 时n=1000 n=3000 n=5000 n=7000 n=9000 n=11000 n=13000 数组大小冒泡排序 简单选择排序 快速排序归并排序非递减数组时间复杂度函数曲线:非递减数组数组大小一冒泡排序-简单选择排序+快速排序归并排序s( 间 时七、实验分析运行环境：Visual C+ 6.0CPU： 2.53GHz 内存：1.92GB系统：Microsoft Windows XP Professional 版本 2002冒泡排序：在最好情况下，待排序记录序列为正序，算法只执行一趟，进行了 n-1次关键码的比较，不需要移动记录，时间复杂度为O(n)；在最坏情况下，待排序记录序列

14、为反序，每趟排序在无序序列中只有一个最大的记录 被交换到最终位置，故算法执行n-1趟，第i (1Win)趟排序执行了 n-i次关键码的比较 和n-i次记录的交换，这样，关键码的比较次数为工(n-i) =n (n-1) /2，记录的移动次数 为3n (n-1) /2，因此，时间复杂度为O(n*n)；在平均情况下，冒泡排序的时间复杂度与最坏情况同数量级。冒泡排序是一种稳定的排序方法。简单选择排序：在选择排序中记录的移动次数较少。在待排序列为正序时，记录的移动次数最少，为 0;第i趟排序需进行n-i次比较，而选择排序需进行n-1趟排序，总比较次数为：E (n-1)= n(n-1)/2=O(n*n)所

15、以，总的时间复杂度为O(n*n),这是简单选择排序最好、最坏、和平均的时间性能。简单选择排序是一种稳定的排序方法。快速排序：在最好情况下，每次划分对一个记录定位后，该记录的左侧子序列与右侧子序列的长 度相同。在具有n个记录的序列中，对一个记录定位要对整个待划分序列扫描一遍，则所需 时间为O(n)。设T(n)是对n个记录的序列进行排序的时间，每次划分后，把待划分区间划 分为长度相等的两个子序列，则有：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)因此，时间复杂度为O(nlogn)。在最坏情况下，待排序记录序列正序或逆序，每次划分只得到一个比上一次划分少一 个记录的子序列(另一个子序列为空)。此时，必须经过n-1次递归调用才能把所有记录定 位，而且第i趟划分需要经过n-i次关键码的比较才能找到第i个记录的基准位置，因此， 总的比较次数为：E(n-i) =n (n-1) /2=O(n*n)记录的移动次数小于等于比较次数。因此，时间复杂度为O(n*n)。在平均情况下，设基准记录的关键码第