2015作业问题讲解.ppt

下载文档

50
0
约8.59千字
约 22页
2016-12-06 发布于四川
举报
版权申诉
保障服务

2015作业问题讲解.ppt

1、本文档共22页，可阅读全部内容。
2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。

2015作业问题讲解

* 设n为正整数，给出下列各种算法关于n的时间复杂度和空间复杂度 ① void fun1(int n) { j=1 ; k=100 ; while(jn) { k=k+1 ; j=j+2 ; } } ② void fun2(int b[n] , n) { for i=0 to n-1 { k=i ; for j=i+1 to n-1 if(b[k]b[j]) k=j ; x=b[i] ; b[i]=b[k] ; b[k]=x ; } } j 取值1、3、5...n/2 时间复杂度：f(n)=O(n) 一个输入变量：n 两个辅助变量：j、k 空间复杂度：O(1) f(n)=(n-1)+(n-2+...+1=n(n-1)/2 时间复杂度：f(n)=O(n2) 四个辅助变量：i、k、j、x n+1个输入变量：b[n]、n 空间复杂度：O(n) Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. ③ void fun3(int n) { j=0 ; s=0 ; while(sn) { j=j+1 ; s=s+j ; } } ④ void fun4(int b[n] , n) { for i=0 to n-1 if(b[i]n) a[n]=b[i]-n ; for i=0 to n-1 b[i]=a[i] ; } s变化：1，1+2，1+2+3，... ∴1+2+3+...+xn 即一个输入变量：n 两个辅助变量：j、s 空间复杂度：O(1) f(n)=n+n 时间复杂度：f(n)=O(n) n+1个输入变量：b[n]、n n+1个辅助变量：i、a[n] 空间复杂度：O(n) x(x+1)/2n x 时间复杂度：f(n)=O( ) Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2.2 试写出在顺序存储结构下逆转线性表的算法，要求使用最少的附加空间。 PROCEDURE RevLst( v , n ) m=int(n/2) for i=1 to m { t=v(i); v(i)=v(n-i+1); v(n-i+1)=t ; } return 2.7 试编写一个算法，将两个有序线性表合并成一个有序线性表 PROCEDURE MergLst( v1 , n1 , v2 , n2 , v ) i=j=k=1 while (i=n1)and(j=n2) do { if v1(i)v2(j) then { v(k)=v2(j) ; j=j+1; } else { v(k)=v1(i) ; i=i+1; } k=k+1 } if ( i=n1) for t=i to n1 do { v(k)=v1(t) ; k=k+1; } if ( j=n2) for t=j to n2 do { v(k)=v2(t) ; k=k+1; } return 或 for i=0 to m-1 { t=v(i) ; v(i)=v(n-i-1) ; v(n-i-1)=t ; } Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Pro