算法时间复杂度.pdf

文档介绍：该【算法时间复杂度 】是由【我是开始】上传分享，文档一共【5】页，该文档可以免费在线阅读，需要了解更多关于【算法时间复杂度 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。实验一算法的时间复杂度
一、实验目的与要求
熟悉C/C++语言的集成开发环境;
通过本实验加深对算法分析基础知识的理解。
二、实验内容:
掌握算法分析的基本方法,并结合具体的问题深入认识算法的时间复杂度分析。
三、实验题
定义一个足够大的整型数组,并分别用起泡排序、简单选择排序、快速排序和归并排序对数组中的
数据进行排序(按从小到大的顺序排序),记录每种算法的实际耗时,并结合数据结构中的知识对
算法的时间复杂度分析进行说明。实验数据分两种情况:
1、数组中的数据随机生成;
2、数组中的数据已经是非递减有序。
四、实验步骤
理解算法思想和问题要求;
编程实现题目要求;
上机输入和调试自己所编的程序;
验证分析实验结果;
整理出实验报告。
五、实验程序
#include<iostream>
#include<>
#include<>
usingnamespacestd;
voidSelectSort(intr[],intn)
{
inti;
intj;
intindex;
inttemp;
for(i=0;i<n-1;i++)
{
index=i;
for(j=i+1;j<n;j++)
if(r[j]<r[index])
index=j;
if(index!=i)
{
temp=r[i];
r[i]=r[index];
r[index]=temp;
}
}
for(i=0;i<n;i++)
cout<<r[i]<<"";
来源于网络
cout<<"\n";
}
voidBubbleSort(intr[],intn)
{
inttemp;
intexchange;
intbound;
exchange=n-1;
while(exchange)
{
bound=exchange;
exchange=0;
for(intj=0;j<bound;j++)
if(r[j]>r[j+1])
{
temp=r[j];
r[j]=r[j+1];
r[j+1]=temp;
exchange=j;
}
}
for(inti=0;i<n;i++)
cout<<r[i]<<"";
cout<<"\n";
}
intPartition(intr[],intfirst,intend)
{
inti=first;
intj=end;
inttemp;
while(i<j)
{
while(i<j&&r[i]<=r[j])
j--;
if(i<j)
{
temp=r[i];
r[i]=r[j];
r[j]=temp;
i++;
}
while(i<j&&r[i]<=r[j])
i++;
if(i<j)
{
temp=r[j];
来源于网络
r[j]=r[i];
r[i]=temp;
j--;
}
}
returni;
}
//快速排序
voidQuickSort(intr[],intfirst,intend)
{
if(first<end)
{
intpivot=Partition(r,first,end);
QuickSort(r,first,pivot-1);
QuickSort(r,pivot+1,end);
}
}
voidMerge(intr[],intr1[],ints,intm,intt)
{
inti=s;
intj=m+1;
intk=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++];
}
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<n-h)
来源于网络
Merge(r,r1,i,i+h-1,n);
elsefor(k=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++)
b[k]=rand()%100;
cout<<b[k]<<"";
cout<<"\n起泡排序结果为:"<<"\n";
BubbleSort(b,numv);
cout<<clock()-t<<"ms"<<endl;
cout<<"\n简单选择排序结果为:"<<"\n";
SelectSort(b,numv);
cout<<clock()-t<<"ms"<<endl;
cout<<"\n快速排序结果为:"<<"\n";
QuickSort(b,0,100);
for(intj=0;j<100;j++)
cout<<b[j]<<"";
cout<<"\n";
cout<<clock()-t<<"ms"<<endl;
constinth=100;
intb1[h];
for(inti=0;i<h;i++)
b1[i]=rand()%k;
inta1[h];
intc1[h];
cout<<"\n归并排序结果为:"<<"\n";
来源于网络
MergeSort2(b1,a1,c1,0,h-1);
for(intm=0;m<h;m++)
cout<<a1[m]<<"";
cout<<"\n";
cout<<(clock()-t)<<"ms"<<endl;
return0;
}
六实验结果
当随机数为10时:
起泡排序结果为:4ms
简单选择排序结果为:7ms
快速排序结果为:12ms
归并排序结果为:16ms
当随机数为100时:
起泡排序结果为:20ms
简单选择排序结果为:41ms
快速排序结果为:61ms
归并排序结果为:82ms
当随机数为1000时:
起泡排序结果为:289ms
简单选择排序结果为:480ms
快速排序结果为:720ms
归并排序结果为:993ms
七、实验分析
通过本实验知道了最快排序的方法,明白了各种排序法的时间复杂度。
来源于网络