算法的时间复杂度 实验报告

实验一 算法的时间复杂度一、实验目的与要求熟悉C/C+语言的集成开发环境；通过本实验加深对算法分析基础知识的理解。软件环境：操作系统：windows7旗舰版集成开发环境 ： visual studio 2010 旗舰版硬件环境：处理器：因特尔 Core i3 M 380内存： 2GB二、实验内容:掌握算法分析的基本方法，并结合具体的问题深入认识算法的时间复杂度分析。三、实验题定义一个足够大的整型数组，并分别用起泡排序、简单选择排序、快速排序和归并排序 对数组中的数据进行排序（按从小到大的顺序排序），记录每种算法的实际耗时，并结合数 据结构中的知识对算法的时间复杂度分析进行说明。实验数据分两种情况：1、数组中的数据随机生成；2、数组中的数据已经是非递减有序。四、实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、实验程序#include #include #include#include/导入时间库函数文件using namespace std;void BubbleSort(int arr,int n);void QuickSort(int arr,int left,int right);void 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;int main(int argc,char *argv) int array_SortARRAY_MAXSIZE; int array_Sort2ARRAY_MAXSIZE; for(int i=0;i=ARRAY_MAXSIZE;i+) array_Sorti=rand()%500; for(int j=0;jARRAY_MAXSIZE;j+) array_Sort2j=j; clock_t start,end; start=clock();/定义数组最大长度/测试调用的排序算法耗时/声明待排序的数组/生成随机数组，大小为10000/生成非递减数组，大小均为10000/声明开始和结束的时间计数器/排序开始时间计数器BubbleSort(array_Sort,ARRAY_MAXSIZE);/起泡排序算法测试end=clock();/排序结束时间计数器COU t随机数组起泡排序测试耗时为：； cout(double)(end-start) msendl;start=ClOCk();QUiCkSOrt(array_SOrt,0,ARRAY_MAXSIZE-1);end=ClOCk();COU t随机数组快速排序测试耗时为：；COUt(dOUble)(end-start) msendl;/快速排序算法测试start=ClOCk();SeleCtSOrt(array_SOrt,ARRAY_MAXSIZE);end=ClOCk();COU t随机数组选择排序测试耗时为：；COUt(dOUble)(end-start) msendl;/选择排序算法测试start=ClOCk()；UniOnSOrt(array_SOrt,0,ARRAY_MAXSIZE-1)； /归并排序算法测试end=clock();COU t随机数组归并排序测试耗时为：； cout(double)(end-start) msarri+1) temp=arri;arri=arri+1;arri+1=temp;exchange二i;/for循环结束时记录的是本趟循环最后交换的位置 /快速排序的定义，需要三个参数待排序数组、数组左边界和右边界 void QuickSort(int arr,int left,int right)/递归结束/进行一次划分/递归对划分后的左侧快速排序/递归对划分后的又侧快速排序if(leftright)int pivot=Partition(arr,left,right);QuickSort(arr,left,pivot-1);QuickSort(arr,pivot+1,right);/选择排序的定义，需要两个参数待排序数组和数组长度void SelectSort(int arr ,int n) int index=0; int temp=0;for(int i=0;in;i+) index=i;for(int j=i+1;j=n;j+) if(arrjarrindex)/记录每次比较中的较小数的位置/交换时的临时变量/默认每次循环时第一个为最小index=j;if(index!=i)/如果当前的最小值不是arri，则和记录位置的值交换temp=arri;arri=arrindex; arrindex=temp; /归并排序的定义，需要三个参数待排序数组、数组左边界和右边界void UnionSort(int arr，int left，int right)if(leftj时本趟循环结束，交换枢纽值和j位置的值/临时使用的辅助数组/一次快速排序 int Partition(int arr,int left,int right ) int i=left;int j=right;int temp=0;dodo i+;while (arriarrleft); if(ij) temp=arri; arri=arrj; arrj=temp;while(i.1 .1 一.-l-lF-fM 包束一羊开 屋快普 nrj nrj rrrj nrj g24-T-T-44-T- T Ss m 5 3 n 3 2 J s0 3 - ；比为 -1 - 斗J 0 n 0 日三 L _F用- 言.-(= 一-HF- 浜速选匸吐掛 S映用暑 rrHmjm律- 丿g JI.-1.I. 数数数数音7 HL 诵遒递迹K -Z - z - z- - -._ L-nllsnlls6 04 0 6s3 3 11内为内为rnM nn - - - TJJsn sms 6宙 E47 n 丄180 2 头为 为为哥 试- - u- I 过过级级-LiJ-lJu 4. !-,-s s Smnrl8 7 115 1s sm msm 7 15 1nn - - - J一声苯三产三试试试试泡速择# 起快选归 -_ -二二-纟?:-?44.- 塾謝数数咆速A归戋 mj m| nfl nr| 津- n 、ls煽理 E-d1p-J1rJ-6ri-ljf .TQ71.11771 i u.-AJLbzI- J - .1 J .1 J-.;!.T. 3E二3E= _冃序序 LrJ二-二- 泡速择开 起快选归 -二- - - -2*:2-?4.七. 裁数靡鄭 -丿f!.!* * -r *2 0 1 : ;.头-rK ?0|!1 试 -1lu- 甘试级期- 电速选口筑 起快用用継 rn| m| m| 一二-a- 数数齧意 瞻黑任 5 rj-nnlLrTV a.Ji.ifg 3E迂EU_H七、实验分析1、各算法时间时间消耗图2、各算法时间性能分析表：方法最好情况最坏情况平均情况起泡排序O(n)O(n2)O(n2)快速排序O(nlog2n)O(n2)O(nlog2n)选择排序O(n2)O(n2)O(n2)归并排序O(nlog2n)O(nlog2n)O(nlog2n)3、分析与说明：由算法时间复杂度表分析，起泡排序在最好情况下时间性能好， 最坏情况和平均情况和选择排序一样，选择排序的时间性能都不高， 均为O(n2),根据平均情况来看，快速排序和归并排序的时间性能一 样，且最坏情况时归并排序优于快速排序。对于随机数组序列，数组大小为 10000，8000，5000 时候，归并 排序算法执行时间和快速排序时间都相对较短，简单选择排序缓慢， 而起泡排序则是最耗时的。但是当数组由 10000 变到 5000 时，归并 排序的时间性能变化不大，而快速排序时间性能提高很多，起泡排序 时间性能下降慢，所以起泡排序在随机序列中的性能不高。对于非递减数组序列，起泡排序时间消耗为均为 0(0 不代表没耗 时，只是 CPU 处理速度太快，没法显示更精确的时间)，而其他的快 速排序，选择排序，归并排序和随机数组序列情况接近。所以起泡排 序在非递减序列中的时间性能高。