《算法导论》习题答案.doc 7页

'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.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