算法时间复杂度.doc

文档介绍：算法的时间复杂度
实验目的与要求
熟悉C/C++语言的集成开发环境；
通过本实验加深对算法分析基础知识的理解。
实验内容:
掌握算法分析的基本方法，并结合具体的问题深入认识算法的时间复杂度分析。
实验题
定义一个足够大1[], int s, int m, int t)
{
int i=s;
int j=m+1;
int k=s;

while (i<=m && j<=t)
{
if (r[i]<=r[j])
r1[k++]=r[i++];
else
r1[k++]=r[j++];
}
if (i<=m)
while (i<=m)
r1[k++]=r[i++];
else
while (j<=t)
r1[k++]=r[j++];
}
void MergeSort2(int r[], int r1[], int r2[],int s, int t)
{

int m;
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);
}
}
int main()
{const int numv=8000;
srand((unsigned)time(NULL));
int i,a[numv],b[numv];
for(i=0;i<numv;i++)
{a[i]=rand()%101;//
b[i]=i;}
int a1[numv];
int a2[numv];
int b1[numv];
int b2[numv];
clock_t start, finish;
double duration;
start = clock();
BubbleSort(a, numv);
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
cout<<"随机数组时"<<"\n"<<"冒泡排序的运行时间为"<<duration<<"ms"<<"\n";
start = clock();
BubbleSort(b, numv);
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;

clock_t start1, finish1;
double duration1;
start1 = clock();
SelectSort(a,numv);
finish1 = clock();
duration1 = (double)(finish1 - start1) / CLOCKS_PER_SEC;
cout<<"简单选择排序的运行时间为"<<duration1<<"ms"<<"\n";
start1 = clock();
SelectSort(b,numv);
finish1 = clock();
duration1 = (double)(finish1 - start1) / CLOCKS_PER_SEC;
clock_t start2, finish2;
double duration2;
start2 = clock();
QuickSort(a,0,numv-1);
finish2 = clock();
duration2 = (double)(finish2 - start2) / CLOCKS_PER_SEC;
cout<<"快速排序的运行时间为"<<duration2<<"ms"<<"\n";
start2 = clock();
QuickSort