《算法导论习题答案》由会员分享，可在线阅读，更多相关《算法导论习题答案（7页珍藏版）》请在金锄头文库上搜索。
1、Chapter2 Getting Start2.1 Insertion sort2.1.2 将Insertion-Sort重写为按非递减顺序排序2.1.3 计算两个n位的二进制数组之和2.2 Analyzing algorithms2.2.1将函数用符号表示2.2.2写出选择排序算法selection-sort当前n-1个元素排好序后，第n个元素已经是最大的元素了.最好时间和最坏时间均为2.3 Designing algorithms 2.3.3 计算递归方程的解（1） 当时，显然有（2） 假设当时公式成立，即，则当，即时， 2.3.4 给出insertion sort的递归版本的递归式2.3
2、-6 使用二分查找来替代insertion-sort中while循环内的线性扫描，是否可以将算法的时间提高到？虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂度依然是2.3-7 给出一个算法，使得其能在的时间内找出在一个n元素的整数数组内，是否存在两个元素之和为x首先利用快速排序将数组排序，时间，然后再进行查找：Search(A,n,x) QuickSort(A,n);i1; jn;while Ai+Ajx and ij if Ai+Ajxii+1 elsejj-1if Ai+Aj=x return trueelse retu
3、rn false 时间复杂度为。或者也可以先固定一个元素然后去二分查找x减去元素的差，复杂度为。Chapter3 Growth of functions3.1Asymptotic notation3.1.2证明对于,时， 对于，时，存在，当时，对于，3.1-4 判断3.1.6 证明如果算法的运行时间为，如果其最坏运行时间为，最佳运行时间为。最坏时间，即；最佳时间，即3.1.7：证明 定义3.2 Standard notation and common functions3.2.2 证明3.2.3证明 3.2.4与是否多项式有界设lgn=m，则 lgn！不是多项式有界的。3.2.5比较lg(lg
4、*n)与lg*(lgn)lg*(lgn)= lg*n-1设lg*n=x，lgxx-1 lg*(lgn)较大。Chapter4 Recurrences4.1 The recursion-tree4.1.1 证明的解为4.1.2 证明的解为设 ，当4.1.3 将假设改为T(n) = cn lgn +b，只需要在T(1)=1的情况下成立。 4.1.6 计算的解令令T(n)=S(m),则其解为4.2 The recursion-tree method4.2.1 4.2.2 略4.2.3 4.2.5 4.3 The master method4.3.1 略4.3.4 主方法是否适用方程，给出该方程解的一个上界不适用使用递归树方法可以求得其一个上界为4.3.5给出某常数和函数，使得其满足主定理case3中除了外的所有条件。， 找不到这样的，总是满足上面的条件，如时，此时，所以不满足。
