IntroductionToAlgorithms算法导论的部分习题解答.doc

Chapter2 Getting Start 2.1 Insertion sort 2.1.2 将Insertion-Sort重写为按非递减顺序排序 2.1.3 计算两个n位的二进制数组之和 2.2 Analyzing algorithms 2.2.1将函数用符号表示 2.2.2写出选择排序算法selection-sort 当前n-1个元素排好序后，第n个元素已经是最大的元素了. 最好时间和最坏时间均为 2.3 Designing algorithms 2.3.3 计算递归方程的解 当时，，显然有 假设当时公式成立，即， 则当，即时， 2.3.4 给出insertion sort的递归版本的递归式 2.3-6 使用二分查找来替代insertion-sort中while循环内的线性扫描，是否可以将算法的时间提高到？ 虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂度依然是 2.3-7 给出一个算法，使得其能在的时间内找出在一个n元素的整数数组内，是否存在两个元素之和为x 首先利用快速排序将数组排序，时间，然后再进行查找： Search(A,n,x) QuickSort(A,n); i←1; j←n; while A[i]+A[j]x and ij if A[i]+A[j]x i←i+1 else j←j-1 if A[i]+A[j]=x return true else return false 时间复杂度为。 或者也可以先固定一个元素然后去二分查找x减去元素的差，复杂度为。 Chapter3 Growth of functions 3.1Asymptotic notation 3.1.2证明对于, 时， 对于， 时， 存在，当时， 对于， 3.1-4 判断 3.1.6 证明如果算法的运行时间为，如果其最坏运行时间为，最佳运行时间为。 最坏时间，即； 最佳时间，即 3.1.7：证明 定义 3.2 Standard notation and common functions 3.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，lgxx-1 lg*(lgn)较大。 Chapter4 Recurrences 4.1 The recursion-tree 4.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 method 4.2.1 4.2.2 略 4.2.3 4.2.5 4.3 The master method 4.3.1 略 4.3.4 主方法是否适用方程，给出该方程解的一个上界 不适用 使用递归树方法可以求得其一个上界为 4.3.5给出某常数和函数，使得其满足主定理case3中除了外的所有条件。 ， 找不到这样的，总是满足上面的条件，如时，，此时，所以不满足。