实验一算法的时间复杂度_第1页
实验一算法的时间复杂度_第2页
实验一算法的时间复杂度_第3页
实验一算法的时间复杂度_第4页
实验一算法的时间复杂度_第5页
已阅读5页,还剩10页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、算法时间复杂度实验 学院:计算机科学与技术 班级: 软 件082班 姓名: 黄 健 学号: 20084350242 算法的时间复杂度一、 实验目的与要求熟悉C/C+语言的集成开发环境;通过本实验加深对算法分析基础知识的理解。二、 实验内容:掌握算法分析的基本方法,并结合具体的问题深入认识算法的时间复杂度分析。三、 实验题定义一个足够大的整型数组,并分别用起泡排序、简单选择排序、快速排序和归并排序对数组中的数据进行排序(按从小到大的顺序排序),记录每种算法的实际耗时,并结合数据结构中的知识对算法的时间复杂度分析进行说明。实验数据分两种情况:1、数组中的数据随机生成;2、数组中的数据已经是非递减有

2、序。四、 实验步骤理解算法思想和问题要求;编程实现题目要求;上机输入和调试自己所编的程序;验证分析实验结果;整理出实验报告。五、 实验程序 #include #includeusing namespace std;void MergeSort(int,int,int);void Merge(int ,int,int,int);int main()int h=0; const int n=5000;int tn;clock_t start,end;clock_t start1,end1;for(int i=0;in;i+)ti=rand()%n;for(int j=0;j100;j+)coutt

3、j ; coutn排序中.endl; coutn数组排序后的前100位:endl;start=clock(); MergeSort(t,0,n-1);end=clock();for(int b=0;b100;b+)couttb ;coutn随机赋值数组的归并排序时间:(end - start)endl; start1=clock(); MergeSort(t,0,n-1); end1=clock();coutn非递减有序数组的归并排序时间:(end1 - start1)endl;return 0;void Merge(int r,int s,int m,int t)int i=s;int j=

4、m+1;int k=s;int r15000; while(i=m&j=t)if(ri=rj)r1k+=ri+;else r1k+=rj+;if(i=j)while(j=t)r1k+=rj+;elsewhile(i=m)r1k+=ri+; if (i=m) while (i=m) r1k+=ri+; else while (j=t) r1k+=rj+; for(int g=s;g=t;g+) rg=r1g; void MergeSort(int r,int s,int t)if (st)int m=(s+t)/2;MergeSort(r,s,m);MergeSort(r,m+1,t); Mer

5、ge(r,s,m,t); int Partition(int , int, int);void QuickSort(int , int, int);int main()int h=0;int t10000;clock_t start,end;clock_t start1,end1;for(int i=0;i10000;i+)ti=rand()%10000; for(int k=0;k100;k+) couttk ; coutn排序中.endl; coutn数组排序后的前100位:endl;start=clock();QuickSort(t,0,i-1);end=clock(); for(int

6、 j=0;j100;j+) couttj ;coutn随机赋值数组的快速排序时间:(end - start)endl;start1=clock();QuickSort(t,0,6359); end1=clock();coutn非递减有序数组的快速排序时间:(end1 - start1)endl;return 0;void QuickSort(int r , int first, int end)int pivot; if (firstend) pivot=Partition(r, first, end); QuickSort(r, first, pivot-1); QuickSort(r, p

7、ivot+1, end); int Partition(int r , int first, int end)int i=first;int j=end; int h;int k;/初始化while (ij) while (ij & ri= rj) j-; /右侧扫描 if (ij) h=ri; ri=rj; rj=h; /将较小记录交换到前面 i+; while (ij & ri= rj) i+; /左侧扫描if (ij) k=ri; ri=rj; rj=k; /将较大记录交换到后面 j-; return i; /i为轴值记录的最终位置void BubbleSort(int,int);int

8、 main()int h=0;int t10000;clock_t start,end;clock_t start1,end1;for(int i=0;i10000;i+)ti=rand()%10000; for(int k=0;k100;k+) couttk ; coutn排序中.endl; coutn数组排序后的前100位:endl;start=clock();BubbleSort(t,10000);end=clock(); for(int p=0;p100;p+) couttp ;coutn随机赋值数组的起泡排序时间:(end - start)endl;start1=clock();Bu

9、bbleSort(t,10000); end1=clock();coutn非递减有序数组的起泡排序时间:(end1 - start1)endl;return 0;void BubbleSort(int r , int n) int exchange;int bound;int m; exchange=n; while (exchange) bound=exchange; exchange=0; for (int j=0; jrj+1) m=rj; rj=rj+1; rj+1=m; exchange=j; void SelectSort(int,int);int main()int h=0;in

10、t t10000;clock_t start,end;clock_t start1,end1;for(int i=0;i10000;i+)ti=rand()%10000; for(int j=0;j100;j+) couttj ; coutn排序中.endl; coutn数组排序后的前100位:endl;start=clock();SelectSort(t,10000);end=clock(); for(int k=0;k100;k+) couttk ; coutn随机赋值数组的简单选择排序时间:(end - start)endl; start1=clock();SelectSort(t,10000); end1=clock();coutn非递减有序数组的简单选择排序时间:(end1- start1)endl;return 0;void SelectSort(int r , int

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论