《算法的时间复杂度实验报告.doc》由会员分享，可在线阅读，更多相关《算法的时间复杂度实验报告.doc（7页珍藏版）》请在三一文库上搜索。
1、 实验一 算法的时间复杂度一、 实验目的与要求熟悉C/C+语言的集成开发环境；通过本实验加深对算法分析基础知识的理解。软件环境： 操作系统：windows7 旗舰版 集成开发环境 ：visual studio 2010 旗舰版 硬件环境： 处理器：因特尔 Core i3 M 380 内存： 2GB二、 实验内容:掌握算法分析的基本方法，并结合具体的问题深入认识算法的时间复杂度分析。三、 实验题定义一个足够大的整型数组，并分别用起泡排序、简单选择排序、快速排序和归并排序对数组中的数据进行排序（按从小到大的顺序排序），记录每种算法的实际耗时，并结合数据结构中的知识对算法的时间复杂度分析进行说明。实
2、验数据分两种情况：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,in
3、t 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+) /生成随机数组，大小为
4、10000array_Sorti=rand()%500;for(int j=0;jARRAY_MAXSIZE;j+) /生成非递减数组，大小均为10000 array_Sort2j=j;clock_t start,end; /声明开始和结束的时间计数器start=clock(); /排序开始时间计数器BubbleSort(array_Sort,ARRAY_MAXSIZE); /起泡排序算法测试end=clock(); /排序结束时间计数器cout随机数组起泡排序测试耗时为：;cout(double)(end-start) msendl;start=clock(); QuickSort(arra
5、y_Sort,0,ARRAY_MAXSIZE-1); /快速排序算法测试end=clock(); cout随机数组快速排序测试耗时为：; cout(double)(end-start) msendl;start=clock(); SelectSort(array_Sort,ARRAY_MAXSIZE); /选择排序算法测试end=clock(); cout随机数组选择排序测试耗时为：; cout(double)(end-start) msendl;start=clock(); UnionSort(array_Sort,0,ARRAY_MAXSIZE-1); /归并排序算法测试end=clock
6、(); cout随机数组归并排序测试耗时为：; cout(double)(end-start) msendl;coutendl;start=clock(); BubbleSort(array_Sort,ARRAY_MAXSIZE); end=clock(); cout非递减数组起泡排序测试耗时为：;cout(double)(end-start) msendl;start=clock(); QuickSort(array_Sort,0,ARRAY_MAXSIZE-1); end=clock(); cout非递减数组快速排序测试耗时为：; cout(double)(end-start) msend
7、l;start=clock(); SelectSort(array_Sort,ARRAY_MAXSIZE); end=clock(); cout非递减数组用选择排序测试耗时为：; cout(double)(end-start) msendl;start=clock(); UnionSort(array_Sort,0,ARRAY_MAXSIZE-1); end=clock(); cout非递减数组用归并排序测试耗时为：; cout(double)(end-start) msendl;system(pause);return 0;/起泡排序的定义，需要两个参数待排数组和数组长度void Bubbl
8、eSort(int arr,int n)int exchange=n; /记录本次交换的位置int bound=0; /每次待排序的到的位置int temp=0; /临时变量存储交换时的一个值while(exchange) bound=exchange;exchange=0;for(int i=0;iarri+1) /判断最近两个并做交换 temp=arri;arri=arri+1;arri+1=temp;exchange=i; /for循环结束时记录的是本趟循环最后交换的位置/快速排序的定义，需要三个参数待排序数组、数组左边界和右边界void QuickSort(int arr,int le
9、ft,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;
10、/默认每次循环时第一个为最小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(leftright) /序列长度超过一，则进行自序列的划分int mid=(left+right)/2; /将待排序列划分为两部分UnionSort(arr,left,mid)
11、; /对左序列进行归并UnionSort(arr,mid+1,right); /对又序列进行归并Union(arr,left,mid,right); /将两个有序序列合并成一个有序的序列/一次快速排序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; /交换当前i和j记录位置的值arri=arrj;arrj=tem
12、p;while(ij) ; /当ij时本趟循环结束，交换枢纽值和j位置的值arrleft=arrj;arrj=temp;return j;/归并排序合并两有序的子序列void Union(int arr,int left,int mid,int right)int temp10000; /临时使用的辅助数组int i=left;int j=mid+1;int k=0;while(i=mid)&(j=right) /比较后把i，j中最小的放入temp中if(arri=arrj)tempk+=arri+;else tempk+=arrj+;while(i=mid)tempk+=arri+;whil
13、e(j=right)tempk+=arrj+;for(i=0,k=left;k=right; )arrk+=tempi+; /把排好序临时数组放回原数组六、 实验结果1.数组大小ARRAY_MAXSIZE为10000如下：2. 数组大小ARRAY_MAXSIZE为8000如下3. 数组大小ARRAY_MAXSIZE为5000如下：七、 实验分析1、 各算法时间时间消耗图2、各算法时间性能分析表：方法最好情况最坏情况平均情况起泡排序O(n)O(n)O(n)快速排序O(nlog2n)O(n)O(nlog2n)选择排序O(n)O(n)O(n)归并排序O(nlog2n)O(nlog2n)O(nlog2
14、n)3、 分析与说明： 由算法时间复杂度表分析，起泡排序在最好情况下时间性能好，最坏情况和平均情况和选择排序一样，选择排序的时间性能都不高，均为O(n)，根据平均情况来看，快速排序和归并排序的时间性能一样，且最坏情况时归并排序优于快速排序。 对于随机数组序列，数组大小为10000，8000，5000时候，归并排序算法执行时间和快速排序时间都相对较短，简单选择排序缓慢，而起泡排序则是最耗时的。但是当数组由10000变到5000时，归并排序的时间性能变化不大，而快速排序时间性能提高很多，起泡排序时间性能下降慢，所以起泡排序在随机序列中的性能不高。 对于非递减数组序列，起泡排序时间消耗为均为0（0不代表没耗时，只是CPU处理速度太快，没法显示更精确的时间），而其他的快速排序，选择排序，归并排序和随机数组序列情况接近。所以起泡排序在非递减序列中的时间性能高。