算法导论复习题答案.doc

《算法导论复习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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给出insert

2、ionsort的递归版本的递归式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、ifA[i]+A[j]

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

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