算法时间复杂度分析排序.docx

算法时间复杂度分析排序.docx

《算法时间复杂度分析排序.docx》由会员分享，可在线阅读，更多相关《算法时间复杂度分析排序.docx（21页珍藏版）》请在冰点文库上搜索。

算法时间复杂度分析排序

算法复杂度分析

作业内容：

选择两个以上（含两个）解决同一个问题的算法，以相同的数据作为输入，分析在自己电脑上实际运行时间，对不同算法时间复杂度的事前分析进行验证。

验证方案与数据自行设计（注意数据规模，如果数据规模太小可能监测不到耗时，另外注意递归算法，递归次数太多也可能没有结果和时间输出）。

比如：

选择三种排序算法，对同一组初始数据进行排序，检测每种算法排序时所消耗的时间，查看结果是否与已知的算法时间复杂度分析相符。

作业请以一个word或wps格式的文档作为附件提交，文档包含三部分内容：

方案设计、程序代码（粘贴入文档中）、运行结果及分析。

作业思路：

先利用随机数函数生成大量数据，再通过调用time.h中的clock（）函数，及CLOCK_PRE_SECOND值，对程序运行时间进行计算，之后对算法进行复杂度分析。

所选算法：

冒泡排序、快速排序

代码：

随机数生成：

#include

#include

#include

#include

usingnamespacestd;

intmain（）

{

freopen（"in.in","w",stdout）;

srand（time（NULL））;

intt=100;

while（t--）

{

intn;

n=1000;

printf（"%d\n",n）;

for（inti=0;i

{

printf（"%d",rand（）%100000000+1）;

}

printf（"\n"）;

}

return0;

}

冒泡排序：

#include

#include

#include

#include

#defineMAX_N100100

usingnamespacestd;

inta[MAX_N];

intmain（）

{

longlongstart,finish;

freopen（"in.in","r",stdin）;

freopen（"bubble.out","w",stdout）;

intn;

start=clock（）;

while（~scanf（"%d",&n））

{

for（inti=0;i

{

scanf（"%d",&a[i]）;

}

for（inti=0;i

{

for（intj=0;j

{

if（a[j]>a[j+1]）

{

inttemp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

}

}

}

for（inti=0;i

printf（"%d",a[i]）;

printf（"\n"）;

}

finish=clock（）;

printf（"RunTime=%.3lfs\n",（double）（finish-start）/CLOCKS_PER_SEC）;

return0;

}

快速排序：

#include

#include

#include

#include

#defineMAX_N100100

usingnamespacestd;

inta[MAX_N];

voidquick（intl,intr）

{

if（l

{

inti=l,j=r,x=a[l];

while（i

{

while（i=x）

j--;

if（i

a[i++]=a[j];

while（i

i++;

if（i

a[j--]=a[i];

}

a[i]=x;

quick（l,i-1）;

quick（i+1,r）;

}

}

intmain（）

{

longlongstart,finish;

freopen（"in.in","r",stdin）;

freopen（"quick.out","w",stdout）;

start=clock（）;

intn;

while（~scanf（"%d",&n））

{

for（inti=0;i

{

scanf（"%d",&a[i]）;

}

quick（0,n-1）;

for（inti=0;i

printf（"%d",a[i]）;

printf（"\n"）;

}

finish=clock（）;

printf（"RunTime=%.3lfs\n",（double）（finish-start）/CLOCKS_PER_SEC）;

return0;

}

结果截图：

1

data.cpp：

In.in:

Quick.out

快速排序时间：

Bubble.out：

冒泡排序时间：

1

data.cpp：

In.in:

Quick.out

快速排序时间：

Bubble.out：

冒泡排序时间：

1

data.cpp：

In.in:

Quick.out

快速排序时间：

Bubble.out：

冒泡排序时间：

1

data.cpp：

In.in:

Quick.out

快速排序时间：

Bubble.out：

冒泡排序时间：

冒泡排序时间复杂度O（n2），快速排序时间复杂度O（nlog（n）），上面分别列出n在[1-100],[1-1000][1-10000],[1-100000]时100组数据的排序耗费的时间。

可以看出冒泡排序非常耗时，而快速排序快得多。

两种排序时间基本符合n2和nlog（n）的增长速率。