算法设计技巧与分析报告问题详解

《算法设计技巧与分析报告问题详解》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准文案算法设计技巧与分析参考答案第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)精彩文档实用标准文案算法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次。精彩文档实用标准文案1.13FTF,TTT,FTF,TFF,FTF1.16(a)执行该算法，元素比较的最少次数是n-1。元素已按非降序排列时候达到最小值。(b)执行该算法，元素比较的最多次数是。元素已按非升序排列时候达到最大值。(c)执行该算法，元素赋值的最少次数是0。元素已按非降序排列时候达到最小值。(d)执行该算法，元素赋值的最多次数是。元素已按非升序排列时候达到最大值。(e)用O符号和符号表示算法BUBBLESORT

4、的运行时间：，(f)不可以用符号来表示算法的运行时间：是用来表示算法的精确阶的，而本算法运行时间由线性到平方排列，因此不能用这一符号表示。1.27不能用关系来比较和增长的阶。∵不是的，即不能用关系来比较和增长的阶。1.32精彩文档实用标准文案(a)当n为2的幂时，第六步执行的最大次数是：时，(b)由(a)可以得到：当每一次循环j都为2的幂时，第六步执行的次数最大，则当（其中取整）时，(c)用符号表示的算法的时间复杂性是已证明n=2k的情况，下面证明n=2k+1的情况：因为有所以n=2k+1时，第六步执行的最大次数仍

5、是nlogn。(d)用符号表示的算法的时间复杂性是。当满足取整为奇数时，算法执行的次数是次，其他情况算法执行次数均大于。(e)O更适合表示算法的时间复杂性。因为本算法时间复杂性从到，而是表示精确阶的。1.38对个数进行排序。精彩文档实用标准文案第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、例5.15.14(a)不稳定，例如：12454524124545244545241245452412可见SELECTIONSORT中相等元素的序在排序后改变。(b)(c)(d)(f)稳定5.17(a)利用取，5.18(a)第6章分治6.3输入：A[1,2,…n]精彩文档实用标准文案输出：max,min1.fori=1tomid2.j=high-i3.ifa[i]>a[j],thenexchangea[i],a[j]4.endfor5.fori=lowtomid6.ifa[i+1]

7、gea[low],a[i+1]7.endfor8.fori=mid+1tohigh9.ifa[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.endif精彩文档实用标准文案9.re

8、turnsum算法需要的工作空间为36.10.精彩文档实用标准文案321514151117255132141515251114151517253251141515321117511125175132151532141514151117111725512551323215151414151511111717252551511225191715371845325