算法时间复杂度.docx

《算法时间复杂度.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

2、题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、实验程序#include#include#includeusingnamespacestd;voidSelectSort(intr[],intn){inti;intj;intindex;inttemp;for(i=0;i

3、{temp=r[i];r[i]=r[index];r[index]=temp;}}for(i=0;ir[j+1]){temp=r[j];r[j]=r[j+1];r[

4、j+1]=temp;exchange=j;}}for(inti=0;i

5、[j]=r[i];r[i]=temp;j--;}}returni;}//快速排序voidQuickSort(intr[],intfirst,intend){if(first

6、{if(r[i]<=r[j])r1[k++]=r[i++];elser1[k++]=r[j++];}if(i<=m)while(i<=m)r1[k++]=r[i++];elsewhile(j<=t)r1[k++]=r[j++];}voidMergePass(intr[],intr1[],intn,inth){inti=0;intk;while(i<=n-2*h){Merge(r,r1,i,i+h-1,i+2*h-1);i+=2*h;}if(i

7、=i;k<=n;k++)r1[k]=r[k];}voidMergeSort2(intr[],intr1[],intr2[],ints,intt){intm;if(s==t){r1[s]=r[s];}else{m=(s+t)/2;MergeSort2(r,r2,r1,s,m);MergeSort2(r,r2,r1,m+1,t);Merge(r2,r1,s,m,t);}}intmain(){intb[100];constintnumv=100;clock_tt=clock();for(intk=0;k<100;k++

8、)b[k]=rand()%100;cout<