算法导论习题答案

《算法导论习题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter2GettingStart2.1Insertionsort2.1.2将Insertion-Sort重写为按非递减顺序排序2.1.3计算两个n位的二进制数组之和2.2Analyzingalgorithms2.2.1将函数用符号表示2.2.2写出选择排序算法selection-sort当前n-1个元素排好序后，第n个元素已经是最大的元素了.最好时间和最坏时间均为2.3Designingalgorithms2.3.3计算递归方程的解（1）当时，，显然有（2）假设当时公式成立，即，则当，即时，2.3.4给出insertionsort的递归版

2、本的递归式2.3-6使用二分查找来替代insertion-sort中while循环内的线性扫描，是否可以将算法的时间提高到？虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂度依然是2.3-7给出一个算法，使得其能在的时间内找出在一个n元素的整数数组内，是否存在两个元素之和为x首先利用快速排序将数组排序，时间，然后再进行查找：Search(A,n,x)QuickSort(A,n);i←1;j←n;whileA[i]+A[j]xandi

3、j←j-1ifA[i]+A[j]=xreturntrueelsereturnfalse时间复杂度为。或者也可以先固定一个元素然后去二分查找x减去元素的差，复杂度为。Chapter3Growthoffunctions3.1Asymptoticnotation3.1.2证明对于,时，对于，时，存在，当时，对于，3.1-4判断3.1.6证明如果算法的运行时间为，如果其最坏运行时间为，最佳运行时间为。最坏时间，即；最佳时间，即3.1.7：证明定义3.2Standardnotationandcommonfunctions3.2.2证明3.2.3证明3.2.

4、4与是否多项式有界设lgn=m，则∴lgn！不是多项式有界的。3.2.5比较lg(lg*n)与lg*(lgn)lg*(lgn)=lg*n-1设lg*n=x，lgx

5、mastermethod4.3.1略4.3.4主方法是否适用方程，给出该方程解的一个上界不适用使用递归树方法可以求得其一个上界为4.3.5给出某常数和函数，使得其满足主定理case3中除了外的所有条件。，找不到这样的，总是满足上面的条件，如时，，此时，所以不满足。