Introduction To Algorithms算法导论的部分习题解答

Chapter2 Getting Start

2.1 Insertion sort

2.1.2 将Insertion-Sort重写为按非递减顺序排序 2.1.3 计算两个n位的二进制数组之和

2.2 Analyzing algorithms

2.2.1将函数n3/1000?100n2?100n?3用符号?表示 2.2.2写出选择排序算法selection-sort

当前n-1个元素排好序后，第n个元素已经是最大的元素了. 最好时间和最坏时间均为?(n2)

2.3 Designing algorithms

2if?????n?2?T(n)??k2T(n/2)?nif???n?2,for?k?1 ?2.3.3 计算递归方程的解

（1） 当k?1时，n?2，显然有T(n)?nlgn

（2） 假设当k?i时公式成立，即T(n)?nlgn?2ilg2i?i?2i，

则当k?i?1，即n?2i?1时，

T(n)?T(2i?1)?2T(2i)?2i?1?i?2i?1?2i?1?(i?1)2i?2i?1lg(2i?1)?nlgn

????T(n)?nlgn ?

2.3.4 给出insertion sort的递归版本的递归式

?(1)if??n?1? T(n)???T(n?1)??(n)if??n?1

2.3-6 使用二分查找来替代insertion-sort中while循环内的线性扫描，是否可以将算法的时间提高到?(nlgn)？

虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂度依然是?(n2)

2.3-7 给出一个算法，使得其能在?(nlgn)的时间内找出在一个n元

素的整数数组内，是否存在两个元素之和为x

首先利用快速排序将数组排序，时间?(nlgn)，然后再进行查找：

Search(A,n,x) QuickSort(A,n); i←1; j←n;

while A[i]+A[j]?x and i

return true else

return false

时间复杂度为?(n)。

或者也可以先固定一个元素然后去二分查找x减去元素的差，复杂度为?(nlgn)。

Chapter3 Growth of functions

3.1Asymptotic notation 3.1.2证明对于b?0,(n?a)b??(nb)

a?0时，(n?a)b?(n?n)b?2bnb

(n?a)b?nb

对于c1?1,c2?2b，c1nb?(n?a)b?c2nb

a?0时，(n?a)b?nb

存在n0??2a，当n?n0时，(n?a)b?(n/2)b

对于c1?2?b,c2?1，c1nb?(n?a)b?c2nb

3.1-4 判断2n?1与22n是否等于O(2n)

3.1.6 证明如果算法的运行时间为?(g(n))，如果其最坏运行时间为O(g(n))，最佳运行时间为?(g(n))。

最坏时间O(g(n))，即T?c2g(n)； 最佳时间?(g(n))，即T?c1g(n)

?T??(g(n))

3.1.7：证明o(g(n))??(g(n))??

定义

3.2 Standard notation and common functions 3.2.2 证明alogc?cloga

bblgalogbc?logbclga?lgclogbalgalgclgb

lgalgc?logbalgc?lgb??????alogbc?clogba

3.2.3

nnlg(n!)??(nlgn)n!??(2)???and???n!?o(n) 证明

lgn!??lgi??lgn?nlgni?1i?1nn?lgi??[lgi?lg(n?i)]??lg[i(n?i)]??lg(i?1i?1i?1i?1nn/2n/2n/2n1)?nlgn?n?nlgn422

??????lg(n!)??(nlgn)

当n>4时，i(n?i)?2，?n!??i(n?i)?2n,?n!??(2n)

2i?1n/2n!?nn,?n!?o(nn)

3.2.4?是否多项式有界 ?lgn??!与??lglgn??！设lgn=m，则m!?2?m()me2m?()m?em(lnm?1)?mlnm?1?nlnlnn

∴lgn！不是多项式有界的。

meme