算法设计与分析-课后习题集答案

由天下分享时间：2024/7/11 4:17:04 加入收藏我要投稿点赞

第一章

3. 最大公约数为1。快1414倍。

程序1-2的while循环体做了10次，程序1-3的while循环体做了14141次（14142-2循环）

8.（1）画线语句的执行次数为

n??logn??。?(logn)。

ij（2）画线语句的执行次数为

???1?i?1j?1k?1n(n?1)(2n?1)3。?(n)。

6（3）画线语句的执行次数为 ?n?。?(n)。

??（4）当n为奇数时画线语句的执行次数为

(n?1)(n?1)， 4n(n?2)2当n为偶数时画线语句的执行次数为。?(n)。

42210.（1）当 n?1 时，5n?8n?2?5n，所以，可选 c?5，n0?1。对于n?n0，

f(n)?5n2?8n?2?5n2，所以，5n2?8n?2??(n2)。

2222（2）当 n?8 时，5n?8n?2?5n?n?2?4n，所以，可选 c?4，n0?8。对于n?n0，

f(n)?5n2?8n?2?4n2，所以，5n2?8n?2??(n2)。

222（3）由（1）、（2）可知，取c1?4，c2?5，n0?8，当n?n0时，有c1n?5n?8n?2?c2n，所

以5n?8n?2??(n)。

11. (1) 当n?3时，logn?n?logn，所以f(n)?20n?logn?21n，g(n)?n?logn?2n。可选

3322c?21，n0?3。对于n?n0，f(n)?cg(n)，即f(n)??(g(n))。 222222logn?n?logn，（2）当 n?4 时，所以 f(n)?n/logn?n，g(n)?nlogn?n。可选 c?1，

n0?4。对于 n?n0，f(n)?n2?cg(n)，即 f(n)??(g(n))。

（3）因为 f(n)?(logn)lognlog(logn)?nlog(logn)，g(n)?n/logn?nlogn2。?n，当 n?4 时，f(n)?ng(n)?nlogn2?n。所以，可选 c?1，n0?4，对于n?n0，f(n)?cg(n)，即 f(n)??(g(n))。

第二章

2-17. 证明：设

n?2i，则 i?logn。

T?n??2T?????2nlogn?2?2T??2???2??log????2nlogn

2222??n??????????n??????n?n????? ?22T????n???2n?logn?log2??2nlogn 2????2????n???2?2nlogn?2n 2????2?? ?22T?????n??nn? ?2?2T??3???2?2?log2??2?2nlogn?2n

22????2??2 ?23T????n???2n?logn?log4??2?2nlogn?2n 3????2????n???3?2nlogn?2n?4n 3??2????

?23T??

?LL ?2kT??i?1??n???2knlogn?2n?4n?L?2n?k?1? k????2?? ?2T?2??2?i?1?nlogn?2n?4n?L?2n?i?2? ?2?4?2nlogn?logn?1???i?2??i?1?n

i?1 ?2n?2nlog2n?2nlogn?log2n?3logn?2n ?nlogn?nlogn

当

2??n?2 时，T?n??2nlog2n。所以，T?n????nlog2n?。

第五章

5-4. SolutionType DandC1(int left,int right) { while(!Small(left,right)&&leftP[m]) left=m+1; else return S(P) } }

5-7. template

int SortableList::BSearch(const T&x,int left,int right) const { if (left<=right) { int m=left+(right-left+1)/3; if (xl[m]) return BSearch(x,m+1,right); else return m; } return -1; }

7．m=left+(right-left+1)/3

不能用：m=(left+right)/3 ，两者不同。

受对半搜索的影响：m=(left+right)/2和m=left+(right-left+1)/2是一样的 9．

4 2462 1356 71 3 012345 5677 0 1 2 -103 4 5 6 7 0 1 1 2 2 3 3 4 4

5 5 6 6 7 0 8 证明：因为该算法在成功搜索的情况下，关键字之间的比较次数至少为??logn??，至多为??logn???1。在不成功搜索的情况下，关键字之间的比较次数至少为??logn???1，至多为??logn???2。所以，算法的最

好、最坏情况的时间复杂度为??logn?。假定查找表中任何一个元素的概率是相等的，为不成功搜索的平均时间复杂度为

1，那么， nE???logn?， n?1I?nE?2n?nE成功搜索的平均时间复杂度为As?n?????1???logn?。

nnn其中，I是二叉判定树的内路径长度，E是外路径长度，并且E?I?2n。

Au?n?? 11. 步数初始时 1 2 3 4 排序结果步数初始时 1 2 3 4 5 排序结果 0 5 [4 [3 [3 [2] 2 2 1 5 2 2 2] 3 3 3 2 8 3 3] 3 3 3 3 3 3 3] 4 4 4 4 4 4 4 5 5 5 5 5 5 5 3 [8 [8 [8 [8 [5] 5 6 2 5] 5] 5] 5] 8 8 7 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 1 [1 [1] 1 1 1 1 1 1] 1 1 1 1 2 1 1 1 1 1 1 3 1 [1 [1 [1 [1] 1 4 1 1] 1] 1] 1 1 5 ∞ ∞ ∞ ∞ ∞

12.（1）证明：当n?0或n?1或n?2时，程序显然正确。当n=right-left+1>2时，程序执行下面的语句： int k=(right-left+1)/3; StoogeSort(left,right-k); StoogeSort(left+k,right); StoogeSort(left,right-k);

①首次递归StoogeSort(left,right-k);时，序列的前2/3的子序列有序。

②当递归执行StoogeSort(left+k,right);时，使序列的后2/3的子序列有序，经过这两次递归排序，使原序列的后1/3的位置上是整个序列中较大的数，即序列后1/3的位置上数均大于前2/3的数，但此时，前2/3的序列并不一定是有序的。

③再次执行StoogeSort(left,right-k);使序列的前2/3有序。经过三次递归，最终使序列有序。所以，这一排序算法是正确的。

（2）最坏情况发生在序列按递减次序排列。

?2n???0????1??0，??2??1，??n??3????1。

?3?logn?1?3?设n?2??，则i?。

log3?1?2?i??4???4??2???n??3??n??1?3?3??n??1??1?9??n??3?1?LL

?9??3???9??i??i?1i?22??i?3????n??3?3?L?3?1

???3???3i?1?3??2??

2i?3i13?? ?22logn?13n1???2log3?1? 222?3?nlog3log3?1

log3?log3??1???n ?????冒泡排序最坏时间复杂度为?n2，队排序最坏时间复杂度为??nlogn?，快速排序最坏时间复杂度为

????nlogn?。所以，该算法不如冒泡排序，堆排序，快速排序。