算法分析与设计作业_第1页
算法分析与设计作业_第2页
算法分析与设计作业_第3页
算法分析与设计作业_第4页
算法分析与设计作业_第5页
已阅读5页,还剩46页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

算法分析与设计作业题

第2章:

22.分别对如下函数完成练习21:

9)SequentialSearch(见程序2-28),分析最坏情况下的执行步数。

程序2-28另一个顺序搜索函数

template<classT>

intSequentialSearch(Ta[],constT&x,intn)

{//在未排序的数组a[0:n-1]中查找x

//如果找到,则返回相应位置,否则返回-1

a[n]=x;//假定该位置有效

inti;

for(i=0;a[i]!=x;i++);

if(i==n)return-1;

returni;

)

答案:

1)template<classT>

intSequentialSearch(Ta[],constT&x,intn)

{//在未排序的数组a[0:n-1]中查找x

//如果找到,则返回相应位置,否则返回-1

a[n]=x;//假定该位置有效

count++;〃对应于a[n]=x;

inti;

count++;//对应于intI;

for(i=0;a[i]!=x;i++)

count++;〃对应于for语句

count++;〃对应于最后一条for语句

count++;//对应于if语句

if(i==n)

(

count++;〃对应于return-1;

return-1;

)

count++;〃对应于returni;

returni;

)

2)

template<classT>

intSequentialSearch(Ta[],constT&x,intn)

{//在未排序的数组a[0:n-1]中查找x

//如果找到,则返回相应位置,否则返回-1

a[n]=x;//假定该位置有效

inti;

for(i=0;a[i]!=x;i++)

count++;

if(i==n)

count=count+5;

return-1;

)

count=count+5;

returni;

3)在最坏的情况下,count的值为n+5;

4)

语句s/e频率总步数

intSequentialSearch(Ta[],constT&x,intn)000

(000

a[n]=x;//假定该位置有效111

inti;111

for(i=0;a[i]!=x;i++);1n+1n+1

if(i==n)return-1;111

returni;111

)000

总计n+5

表12-28程序在最坏的情况的执行步数

10)Selections。"(见程序2-7),分析最好和最坏情况下的执行步

数。

程序2-7选择排序

template<classT>

voidSelectionSort(Ta[],intn)

{〃对数组a[0:n-1]中的n个元素进行排序

for(intsize=n;size>l;size—)

(

intj=Max(a,size);

Swap(a[j],a[size-l]);

)

)

答案:

1)template<classT>

voidSelectionSort(Ta[],intn)

{//对数组a[0:n-1]中的n个元素进行排序

for(intsize=n;size>l;size—)

(

count++;〃对应for语句

intj=Max(a,size);

count++;〃对应intj=Max(a,size);

Swap(a[j],a[size-1]);

count++;〃对应Swap(a[j],a[size-1]);

)

count++;〃对应最后一条for语句

)

2)template<classT>

voidSelectionSort(Ta[],intn)

(〃对数组a[0:n-1]中的n个元素进行排序

for(intsize=n;size>l;size—)

(

intj=Max(a,size);

Swap(a[j],a[size-l]);

count=count+3;

)

count++;〃对应最后一条for语句

)

3)在最好的情况和最坏的情况下程序结束时的count值均为3n-2;

4)

语句s/e频率总步数

voidSelectionSort(Ta[],intn)000

(000

for(intsize=n;size>l;size―)1nn

(000

intj=Max(a,size);1n-1n-1

Swap(a[j],a[size-1]);1n-1n-1

)000

)000

总计3n-2

表22-7程序在最好和最坏的情况下的执行步数

11)SelectionSort(见程序2-12),分析最好和最坏情况下的执行

步数。

程序2-12及时终止的选择排序

template<classT>

voidSelectionSort(Ta[],intn)

{//及时终止的选择排序

boolsorted=false;

for(intsize=n;!sorted&&(size>l);size—)

(

intpos=0;

sorted=true;

//找最大元素

for(inti=l;i<size;i++)

if(a[pos]<=a[i])pos=i;

elsesorted=false;//未按序排列

)

Swap(a[pos],a[size-1]);

)

)

答案:

1)template<classT>

voidSelectionSort(Ta[],intn)

{//及时终止的选择排序

boolsorted=false;

count++;//对应于boolsorted=false;

for(intsize=n;!sorted&&(size>l);size—)

(

count++;〃对应于for语句

intpos=0;

count++;〃对应于intpos=0;

sorted=true;

count++;〃对应于sorted=true;

for(inti=l;i<size;i++)

I

count++;〃对应于嵌套的for语句

count++;//对应于if语句

if(a[pos]<=a[i])

pos=i;

count++;//对应于pos=i;

)

else

(

sorted=false;

count++;〃对应于sorted=false;

)

)

count++;〃对应于嵌套for语句的最后一条

count++;〃对应于Swap(a[pos],a[size-1]);

Swap(a[pos],a[size-1]);

)

count++;〃对应于for语句的最后一条

)

2)template<classT>

voidSelectionSort(Ta[],intn)

{//及时终止的选择排序

boolsorted=false;

for(intsize=n;!sorted&&(size>l);size―)

intpos=0;

sorted=true;

for(inti=l;i<size;i++)

(

if(a[pos]<=a[i])

(

pos=i;

count=count+3;

)

else

(

sorted=false;

count=count+3;

)

)

Swap(a[pos],a[size-1]);

count=count+5;

}

count=count+2;

)

3)在最好的情况下count的值为3n+4,在最坏的情况下count的值为

n(3n-l)/2+4n-2

4)

语句s/e频率总步数

voidSelectionSort(Ta[],intn)000

{//及时终止的选择排序000

boolsorted=false;111

for(intsize=n;!sorted&&(size>l);size―)122

(000

intpos=0;111

sorted=true;111

for(inti=l;i<size;i++)1nn

000

if(a[pos]<=a[i])1n-1n-1

pos=i;1n-1n-1

elsesorted=false;000

1000

Swap(a[pos],a[size-1]);111

)000

)000

总计3n+4

表32-12程序在最好的情况下的执行步数

语句s/e频率总步数

voidSelectionSort(Ta[],intn)000

{//及时终止的选择排序000

boolsorted=false;111

for(intsize=n;!sorted&&(size>l);size—)1nn

{000

intpos=0;1n-1n-1

sorted=true;1n-1n-1

for(inti=l;i<size;i++)1n(n+1)/2n(n+1)/2

(000

if(a[pos]<=a[i])1n(n-1)/2n(n-1)/2

pos=i;000

elsesorted=false;0n(n-1)/2n(n-1)/2

)000

Swap(a[pos],a[size-1]);1n-1n-1

)000

)000

总计n(3n-l)/2+4n-2

表42-12程序在最坏的情况下的执行步数

12)InsertionSort(见程序2-14),分析最坏情况下的执行步数。

程序2-14插入排序

template<classT>

voidInsert(Ta[],intn,constT&x)

{//向有序数组a[0:n-1]中插入元素x

inti;

for(i=n-l;i>=0&&x<a[i];i-)

a[i+1]=a[i];

a[i+1]=x;

)

template<classT>

voidInsertionSort(Ta[],intn)

{//对a[0:n-1]进行排序

for(inti=l;i<n;i++)

(

Tt=a[i];

Insert(a,i,t);

}

)

答案:

1)template<classT>

voidInsert(Ta[],intn,constT&x)

{//向有序数组a[0:n-1]中插入元素x

inti;

count++;

for(i=n-l;i>=0&&x<a[i];i-)

(

count++;

a[i+1]=a[i];

count++;

)

count++;

count++;

a[i+1]=x;

)

template<classT>

voidInsertionSort(Ta[],intn)

{//对a[0:n-1]进行排序

for(inti=l;i<n;i++)

(

count++;

count++;

Tt=a[i];

Insert(a,i,t);

)

count++;

)

2)template<classT>

voidInsert(Ta[],intn,constT&x)

{//向有序数组a[0:n-1]中插入元素x

inti;

for(i=n-l;i>=0&&x<a[i];i-)

(

a[i+1]=a[i];

count=count+2;

)

a[i+1]=x;

count=count+3;

)

template<classT>

voidInsertionSort(Ta[],intn)

{//对a[0:n-1]进行排序

for(inti=l;i<n;i++)

Tt=a[i];

count=count+2;

Insert(a,i,t);

)

count++;

)

3)在最坏的情况下程序结束时的count值为(n+5)(n-l)+l;

4)

语句s/e频率总步数

voidInsertionSort(Ta[],intn)000

{//对a[0:n-1]进行排序000

for(inti=l;i<n;i++)1nn

(000

Tt=a[i];1n-1n-1

Insert(a,i,t);n+3(n+3)(n-1)(n+3)(n-1)

)000

)000

总计(n+5)(n-l)+l

表52-14程序在最坏的情况下的执行步数

36.下面哪些规则是正确的?为什么?

(6){f(n)=Q(F(n)),g(n)=Q(G(n))}->f(n)/g(n)=0(F(n)/G(n))

(7){f(n)=0(F(n)),g(n)=0(G(n))}-*f(n)/g(n)=0(F(n)/G(n))

(8){f(n)=0(F(n)),g(n)=0(G(n))}->f(n)/g(n)=。(F(n)/G(n))

(9){f(n)=0(F(n)),g(n)=0(G(n))}-»f(n)/g(n)=O(F(n)/G(n))

答案:

(6)是错误的,⑺⑻⑼是正确的.

在(6)中,因为函数的下限是不确定的,只要符合Q(F(n))<=0

(F(n))就可以了,所以当f(n)较之g(n)的范围要大时,则f(n)/g(n)<

0(F(n)/G(n)),右边的等式是不成立的。

在⑺中,因为。(F(n))既是上限也是下限值,所以其值或者其值

的数量级是不变的,则f(n)/g(n)=0(F(n)/G(n))成立。又由。(F(n))

既是上限也是下限值可得(8)(9)也必然成立。

53.对于n=10,20,30,100,确定函数Transpose(见程序2-22

的运行时间。用表格和图的形式给出测量结果。

程序2-22矩阵转置

template<classT>

voidTranspose(T**a,introws)

{//对矩阵a[0:rows-1][0:rows-1]进行转置

for(inti=0;i<rows;i++)

for(intj=i+l;j<rows;j++)

Swap(a[i][j],a[j][i]);

答案:算法运行后测量结果如下:

C:WINDOWS\system32\cmd.exe-|p|x

数为

勺运

1隹

,什>

H-10S~Y/:

/-一trBl

数为&t秒

当u0.0117333

4隹^/.*

^日

幺20

1y勺

,-巨.B~:

/>一t

、秒

数为0.0245841

A隹i.^*

幺0

H-巨3"^

/'.T勺rBl:

/B+、秒

数为0.0536381

M--L隹40^S*

O日

/J一,:0.0944254秒

数为84-

一'

巨^

-幺50/-4*

M£V日

一:

/t7」秒

数为S.147225

阵BH-

>L生60.-*

!-nt£^^日

/>,-J.x3:

数为

幺工秒

当0.212

A巨7004--

二8*

-1日

/、7:

^、

数为

&+运秒

当0.286908

隹0

A目.8^>^*

-二&

/、^-urBl:

、0.374908

数为

90、

-隹.

二*

M^^日

/、n:

-、

夕秒

箭0.474362

数为

1B+爬

.,W「

10断--

/-\一,!.'T

键继

任.秒

卖0.584991

』H

二K

产S

V/1*.—>

row时间(ms)

100.0117333

200.0245841

300.0536381

400.0944254

500.147225

600.2112

700.286908

800.374908

900.474362

1000.584991

程序2-22的测试结果(表)

第13章:

2.考虑例13-4的找零钱问题,假设售货员只有有限的25美分,10美

分,5美分和1美分的硬币,给出一种找零钱的贪婪算法。这种方法总

能找出具有最少硬币数的零钱吗?证明结论。

(例13-4[找零钱]一个小孩买了价值少于1美元的糖,并将1美

元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提

供了数目不限的面值为25美分、10美分、5美分、及1美分的硬币。售

货员分步骤组成要找的零钱数,每次加入一个硬币。选择硬币时所采

用的贪婪准则如下:每一次选择应使零钱数尽量增大。为保证解法的

可行性(即:所给的零钱等于要找的零钱数),所选择的硬币不应使

零钱总数超过最终所需的数目。

假设需要找给小孩67美分,首先入选的是两枚25美分的硬币,第

三枚入选的不能是25美分的硬币,否则硬币的选择将不可行(零钱总

数超过67美分),第三枚应选择10美分的硬币,然后是5美分的,最

后加入两个1美分的硬币。)

答:此时的一种贪婪算法是:

已知:现有的钞票面额和付款额:

intm[]={25,10,5,1);

intV;〃可由用户输入

输出:各种币值的钞票数intn[4];使得钞票总额为V并且钞票数最少

算法可描述为:

voidPay(intm[],intV)

inti,R,n[4];

for(i=0;i<4;i++)

n[i]=0;

R=V;

i=0;

while(R>0)

(

if(m[i]<=R)

R-=m[i];

n[i]++;

)

else

i++;

for(i=0;i<4;i++)

逐个输出n[i]个m[i]面值的钞票;

这种方法并非总能找出具有最少硬币数的零钱,它虽然符合人们

平时的做法,但是人们往往并不在意所付的零钱数是不是最少。例如

我现在有1张25美分,3张10美分,5张1美分的钞票,当我需要向用户

30美分的零钱时,按照算法应当给1张25美分和5张1美分,总共6张零

钱,但实际上只需给他3张10美分即可。由此可证明该方法并非总能

找出具有最少硬币数的零钱。

*31.1)给出Prim算法(如图13-14所示)的一种正确性证明。

2)将图13-14细化为一个C++程序UNetwork::Prim,其复杂性应为

0(u2)。

3)证明程序的复杂性确实是0(成)。

Prim最小生成树算法:

〃假设网络中至少具有一个顶点

设病所选择的边的集合,初始化户。

设T惆已在树中的顶点的集合,置T修{1}

令联网络中边的集合

泌"e(东>巾)&&(1710/2-1)

令(〃/)为最小代价边,其中〃£7匕v^TV

if(没有这种边)break;

B=E-{{u,力}〃从丹删除此边

在外加入边(〃,0)

}

if(171==n-l)跟一棵最小生成树

else网络是不连通的,没有最小生成树

答案:(1)正确性证明:

首先建立以下的假设:1、只要生成树存在,则普里姆算法就一定

能够产生一个生成树;2、所产生的生成树具有最小的耗费。

设G是任意一个无向的加权图,从12.11.3节可知当且仅当一个无

向图连通时它有生成树。当找不到一条边可以将不在TV中的节点与在

TV中的顶点连接起来的时候,普里姆算法才会失败,而这种情况只有

当该图为非连通图时才会出现,所以说假设1是成立的。

再来证明普里姆算法所产生的生成树具有最小的耗费:当图G具有

有限个数量的生成树时,这其中至少有一个是具有最小耗费的。假设

U是最小耗费的生成树,I和U都具有n-l条边,如果1=11时,则无需

证明就可得知I是具有最小耗费的,假设2得证。那么设I!=U,变量

k<n-l,将这k条边先加到I中去,并且这k条边都在U中,再将第k+1

条不在U中的边加到I中。应该看到,当U转化成I时U和I具有相同的耗

费。这种转化最多执行n-1-k步,每一步k的值都会至少加1,所以转

化后U的值不会改变。因此,当n-1-k步的转化后U和其原先的一样具

有相同的耗费,并且转化将这些边都加到了I中去,所以I是具有最小

耗费的。这每一步的转换将边e加入到U中,又将边f从U中移除,e和f

是按照以下的方法来进行挑选的:

(a)将第k+1条边添加到I中,根据k的定义,这条边是不可能在U中

的,然后在e被添加进来之前把TV中的顶点均作为树中顶点的集合。

而集合R则是剩余顶点(未添加到树中)的集合。边e所连接的两个顶

点分别在TV和R中。

(b)当e被添加到U中时,会产生一条环路。这种情况下,设f是在该

环路中的一条边(当然不会是e),该边所连接的两个顶点分别在TV

和R中。而且连接TV中的一个点和R中一个点的边一定是存在于这个环

路中,所以f不可能是最初添加到I中的那k+1条边,因为与此同时,

作为添加到I中的第k+1条边,e被添加进的边的集合I中没有一条边可

以将TV中的顶点和R中的顶点连接起来。

以上说明V=U+{e}-{f}是一个生成树并且至少会有k+1条边被

添加到I和V中。需要说明的就是V的耗费应当和U的耗费一样。可以看

到,V的耗费是U的耗费乘以e再除以f的耗费,如果e的耗费少于f,那

么生成树V较之U将具有更小的耗费量,这是不可能成立的;如果e的

耗费多于f那么在该算法中f比e更先被添加到I中,但是这种情况也不

存在,所以可以确定,边e和f其实是具有相同耗费的,则可得出结论:

V和U具有相同的耗费。“所产生的生成树具有最小的耗费”也得以证

明。

(2)首先定义两个节点的类:

template<classT>

classVertexNodel{

friendUNetwork<T>;

public:

operatorT()const{returndistance;}

private:

Tdistance;//与最近的节点的距离

intnbr;//树中最近的节点

);

template<classT>

classVertexNode2{

friendUNetwork<T>;

friendModifiedMinHeap<T>;

public:

operatorT()const{returndistance;}

private:

Tdistance;〃与最近的节点的距离

intID;〃节点号

);

接着定义类ModifiedMinHeap.函数Decrease()实现的功能是

将一个更小的节点来替换以前的节点.x.ID该节点,

x.distance是它的新的距离值,该值较之以前的值要更小:

template<classT>

classModifiedMinHeap{

public:

ModifiedMinHeap(intMinHeapSize=10);

~ModifiedMinHeap(){delete[]heap;}

intSize()const{returnCurrentSize;}

TMin(){if(CurrentSize==0)

throwOutOfBounds0;

returnheap[1];}

ModifiedMinHeap<T>&Insert(constVertexNode2<T>&

x);

ModifiedMinHeap<T>&DeleteMin(VertexNode2<T>&

x);

ModifiedMinHeap<T>&Decrease(const

VertexNode2<T>&x);

private:

intCurrentSize,MaxSize;

VertexNode2<T>*heap;〃存放树中节点元素的数组

int*location;〃记录位置的数组

);

template<classT>

ModifiedMinHeap<T>::

ModifiedMinHeap(intMinHeapSize)

{〃生成最小堆

MaxSize=MinHeapSize;

heap=newVertexNode2<T>[MaxSize+1];

location=newint[MaxSize+1];

for(inti=1;i<=MinHeapSize;i++)

location[i]=0;〃初始化,没有元素被定位

CurrentSize=0;

)

template<classT>

ModifiedMinHeap<T>&ModifiedMinHeap<T>::Insert

(constVertexNode2<T>&x)

{〃将x插入到堆里面

if(CurrentSize==MaxSize)

throwNoMem();//nospace

if(x.ID<1||x.ID>MaxSize)

throwBadlnput0;

〃为x找到合适的空间

inti=++CurrentSize;

while(i!=1&&x<heap[i/2]){

〃当不能将x放入heap⑴中时

heap[i]=heap[i/2];//moveelementdown

location[heap[i].ID]=i;

i/=2;〃指向父节点

)

heap[i]=x;

location[x.ID]=i;

return*this;

)

template<classT>

ModifiedMinHeap<T>&ModifiedMinHeap<T>::DeleteMin

(VertexNode2<T>&x)

{//将x设为最小的元素并且删除

if(CurrentSize==0)〃检查堆是否空

throwOutOfBounds();

x=heap[1];

location[x.ID]=0;

〃重新构建堆

VertexNode2<T>y=heap[CurrentSize—];//last

element

inti=1,〃堆中的当前节点

ci=2;//i的孩子节点号

while(ci<=CurrentSize){

//heap[ci]应当比i的孩子节点要大

if(ci<CurrentSize&&

heap[ci]>heap[ci+1])ci++;

〃检查是否可以将y添加到堆中去

if(y<=heap[ci])break;

heap[i]=heap[ci];

location[heap[i].ID]=i;

i=ci;

ci*=2;

)

heap[i]=y;

location[y.ID]=i;

return*this;

)

template<classT>

ModifiedMinHeap<T>&ModifiedMinHeap<T>::Decrease

(constVertexNode2<T>&x)

{〃将x.ID的距离减小至x.distance.

if(!location[x.ID])〃检查x.ID是否在堆中

throwBadlnput0;

〃确认新的距离更小

if(x.distance>=heap[location[x.ID]].distance)

throwBadlnput0;

inti=location[x.ID];

while(i!=1&&x<heap[i/2]){

〃不能将x放入堆中

heap[i]=heap[i/2];〃则将该元素下移

location[heap[i].ID]=i;

i/=2;

)

heap[i]=x;

location[x.ID]=i;

return*this;

)

template<classT>

boolUNetwork<T>::Prim(EdgeNode<T>t[])

{〃普里姆算法,核心是找到一个最小的耗费生成树并返回该

〃树,否则返回false

intn=Vertices0;

bool*selected=newbool[n+1];

VertexNodel<T>*VN1=newVertexNodel<T>[n+1];

VN1[1].distance=0;

for(inti=2;i<=n;i++){

VN1[i].distance=-1;

selected[i]=false;

)

InitializePos0;〃构造图

intv;

Tw;//edgeweight

VertexNode2<T>VN2;//usedformodifiedminheap

ModifiedMinHeap<T>*H;

H=newModifiedMinHeap<T>(n);

First(1,v,w);

while(v){

VN1[v].distance=w;

VN1[v].nbr=1;

VN2.ID=v;

VN2.distance=w;

H->Insert(VN2);

Next(1,v,w);

)

//为生成树选择n-l个顶点

for(inti=0;i<n-1;i++)

〃得到最近的为被选过的节点

try{H->DeleteMin(VN2);}

catch(OutOfBounds)

{〃没有节点可选

returnfalse;

)

EdgeNode<T>x;

intu=VN2.ID;

X.u=u;

x.v=VN1[u].nbr;

x.weight=VN1[u].distance;

t[i]=x;

selected[u]=true;

〃更新距离大小

First(u,v,w);

while(v){

//VN1[v].distance被改变了

if('selected[v]){

if(VN1[v].distance==-1){

〃v不在最小堆中时

VN1[v].distance=w;

VN1[v].nbr=u;

VN2.distance=w;

VN2.ID=v;

H->Insert(VN2);

}

elseif(VN1[v].distance>w)

//v在最小堆中时

VN1[v].distance=w;

VN1[v].nbr=u;

VN2.distance=w;

VN2.ID=v;

H->Decrease(VN2);

)

Next(u,v,w);

)

)

DeactivatePos0;

delete[]VN1;

delete[]selected;

deleteH;

returntrue;

)

测试代码:

#include<iostream>

#include"Iwg.h"

usingnamespacestd;

voidmain()

(

LinkedWGraph<int>G(7);

EdgeNode<int>t[7];

intn=7;

inte,u,v,w;

cout<〈"请输入有个顶点的无向图的边数:"«endl;

cin»e;

for(inti=1;i<=e;i++){

cout<<"请输入边"«i«endl;

cin»u»v»w;

G.Add(u,v,w);

)

cout«"输入的图为:"«endl;

G.Output0;

if(G.Prim(t))

(

cout«"最小生成树的边为:"endl;

for(inti=0;i<n-l;i++)

cout«t[i]«endl;

)

else

cout<〈"该图是非连通的!!"<<endl;

经过测试(无向图设为7条边,依次输入每条边所连接的顶点、

权值),得出测试结果如下(图的表示形式是连通矩阵):

(3)最小堆的插入和删除操作数为0(n),而减小距离(耗费)的

操作数为0(e),所以总时间为0((n+e)logn).如果使用邻接表的话,

花在其余代码上的时间为0(n+e);如果使用邻接矩阵的话(本程序中

就是使用的邻接矩阵),花在其余代码上的时间为n(n2),所以总时

间应当是0(n21ogn)。

第14章:

21.设计一个在最差情况下性能最好的排序算法。

1)比较插入排序、冒泡排序、选择排序、堆排序、归并排序和快速

排序在最坏情况下的运行时间。导致插入排序、冒泡排序、选择排序

和快速排序出现最坏复杂性的输入数据很容易产生。试编写一个程

序,用来产生导致归并排序出现最坏复杂性的输入数据。这个程序本

质上是将〃个排好序的元素“反归并”。对于堆排序,用随机产生的

输入序列来估算最坏情况下的时间复杂性。

2)利用1)中的结果设计一个混合排序函数,使其在最坏情况下具有

最佳性能。比如混合函数可以只包含归并排序和插入排序。

3)测试混合排序函数在最坏情况下的运行时间,并与原排序函数进

行比较。

4)用一个简单的图表来列出七种排序函数在最差情况下的运行时

间。

答案:

(l)a,插入排序最坏时间测试结果:

b、冒泡排序最坏时间测试结果:

困C:'WINDOWSsystein32cin(l.exe-|p|x|

冒¥

R^:

、3

n-10<B-

B4"坏Bt

、V0.00866032

2、

0k.—

警I

坏BtB10.0270984

30k¥-二

、0.0572698

B^-「

40、

¥日」

坏0.099454

Bt、

、&t

50什"

警k

、-X0.153651

60¥'日

、0.219581

B'+坏04'

7S、

=3¥Bl

、0.297524

Bd*-

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论