算法设计技巧和分析答案解析

算法设计技巧和分析答案解析

ID:21802930

大小:361.50 KB

页数:16页

时间:2018-10-24

算法设计技巧和分析答案解析_第1页
算法设计技巧和分析答案解析_第2页
算法设计技巧和分析答案解析_第3页
算法设计技巧和分析答案解析_第4页
算法设计技巧和分析答案解析_第5页
资源描述:

《算法设计技巧和分析答案解析》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、WORD资料下载可编辑算法设计技巧与分析参考答案第1章算法分析基本概念1.1(a)6(b)5(c)6(d)61.4算法执行了7+6+5+4+3+2+1=28次比较453324451212241245454545454545333333333333332424242424244545454545451212121212121212121212242424241212121212121224242445241212121.5(a)算法MODSELECTIONSORT执行的元素赋值的最少次数是0,元素已按非降序排列的时候达到最小值。

2、(b)技术资料专业分享WORD资料下载可编辑算法MODSELECTIONSORT执行的元素赋值的最多次数是,元素已按非升序排列的时候达到最小值。1.7431256729344444333334121212121212555556667724321次9761次2次2次6次2次2次由上图可以看到执行的比较次数为1+1+2+2+2+6+2=16次。1.111924751917131211815458111317219134811151271571217521119517248137151221719513114815127比较均为1

3、次,共5次比较为3次,2次,1次比较为6次比较9次由上图可以得出比较次数为5+6+6+9=26次。技术资料专业分享WORD资料下载可编辑1.13FTF,TTT,FTF,TFF,FTF1.16(a)执行该算法,元素比较的最少次数是n-1。元素已按非降序排列时候达到最小值。(b)执行该算法,元素比较的最多次数是。元素已按非升序排列时候达到最大值。(c)执行该算法,元素赋值的最少次数是0。元素已按非降序排列时候达到最小值。(d)执行该算法,元素赋值的最多次数是。元素已按非升序排列时候达到最大值。(e)用O符号和符号表示算法BUBBL

4、ESORT的运行时间:,(f)不可以用符号来表示算法的运行时间:是用来表示算法的精确阶的,而本算法运行时间由线性到平方排列,因此不能用这一符号表示。1.27不能用关系来比较和增长的阶。∵不是的,即不能用关系来比较和增长的阶。1.32技术资料专业分享WORD资料下载可编辑(a)当n为2的幂时,第六步执行的最大次数是:时,(b)由(a)可以得到:当每一次循环j都为2的幂时,第六步执行的次数最大,则当(其中取整)时,(c)用符号表示的算法的时间复杂性是已证明n=2k的情况,下面证明n=2k+1的情况:因为有所以n=2k+1时,第六步

5、执行的最大次数仍是nlogn。(d)用符号表示的算法的时间复杂性是。当满足取整为奇数时,算法执行的次数是次,其他情况算法执行次数均大于。(e)O更适合表示算法的时间复杂性。因为本算法时间复杂性从到,而是表示精确阶的。1.38对个数进行排序。技术资料专业分享WORD资料下载可编辑第5章归纳法5.3(本题不仅有以下一个答案)1.max(n)过程:max(i)ifn=1returna[1]t=max(i-1)ifa[i-1]>treturna[i-1]elsereturntendif5.6最多次数:最少次数:C(n)=n-15.7技

6、术资料专业分享WORD资料下载可编辑参考例5.15.14(a)不稳定,例如:12454524124545244545241245452412可见SELECTIONSORT中相等元素的序在排序后改变。(b)(c)(d)(f)稳定5.17(a)利用取,5.18(a)第6章分治6.3输入:A[1,2,…n]技术资料专业分享WORD资料下载可编辑输出:max,min1.fori=1tomid2.j=high-i3.ifa[i]>a[j],thenexchangea[i],a[j]4.endfor5.fori=lowtomid6.ifa

7、[i+1]a[high],thenexchangea[high],a[i+1]10.endfor6.5输入:一个整数数组A[1,2,…,n]输出:sum1.ifhigh-low=1then2.sum=a[low]+a[high]3.else4.mid=(low+high)/25sum1=sum(low,mid)6sum2=sum(mid+1,high)7.sum=sum1+sum28.en

8、dif技术资料专业分享WORD资料下载可编辑9.returnsum算法需要的工作空间为36.10.技术资料专业分享WORD资料下载可编辑3215141511172551321415152511141515172532511415153211175111251751321515

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。