@TOC
- 2.1-1 说明INSERTION-SORT在数组A=<31,41,59,26,41,58>上的执行过程。
a. <31,41,59,26,41,58>
b. <31,41,59,26,41,58>
c. <31,41,59,26,41,58>
d. <26,31,41,59,41,58>
e. <26,31,41,41,59,58>
f. <26,31,41,41,58,59>
- 2.1-2 重写过程INSERTION-SORT，使之按非升序排序。
for i=2 to A.length
key = a[i]
j = i - 1
while j>0 and a[j]<key
A[j+1] = A[j]
j = j - 1
A[j+1] = key- 2.1-3 考虑以下查找问题：
输入：n个数的一个序列A=<a1,a2,a3,...,an>和一个值v。
输出：下标i使得v=A[i]或者当v 不在A中出现时，v为特殊值NIL。
for i=1 to n
if v = A[i]
return i;
return NIL;证明循环不定式成立：
初始化：迭代之前，其子数组为空，没有找到继续循环，循环不定式成立。
保持：如果A[1...i-1]不包含v，我们比较A[i]与v。相等则返回i，不等则进行下一步。
终止：i>A.length，则A中肯定不包含v，返回NIL。
- 2.1-4 把两个n为二进制整数加起来，这两个整数分别存储在两个n元数组A和B中。这两个整数的和应按照二进制形式存储在一个（n+1）元数组C中。
ADD_BINARY(A,B):
C = new integer[A.length + 1]
temp = 0
for i=1 to A.length
C[i] = (A[i] + B[i] + temp) % 2
temp = (A[i] + B[i] + temp) / 2
C[i+1] = temp
return C@TOC
- 2.2-1 表示函数n^3 / 1000 - 100n^2 -100n + 3。
n^3 / 1000 - 100n^2 -100n + 3 = O(n^3)
- 2.2-2 写出选择排序算法的伪代码。该算法维持的循环不定式是什么？为什么只需要对前n-1个元素，而不是对所有n个元素运行？给出选择排序的最好情况和最坏情况运行时间。
SELECT_SORT(A,n):
for i=0 to n-1
min = i
for j=i+1 to n
if A[j] < A[min]
min = j
if min != j
swap(A[i],A[min]) //交换A[i]和A[min]
证明循环不定式成立：
初始化：迭代之前，子数组为空，循环不定式成立。
保持：当迭代至第 i 时，子数组A[1,...,i-1]已按序排列，for循环的下一次迭代增加i将保持循环不定式。
终止：当i迭代至i=n-1时，A[1-n]都按序排列。
每次迭代都是找出A[i-n]中的最小元素，在经过n-1次后，剩下的最后一个元素一定为A中的最大元素。
最好情况与最坏情况均为O(n^2)
- 2.2-3 再次考虑现行查找问题（练习2.1-3）。假定要查找的元素等可能的为数组中的任意元素，平均需要检查输入序列的多少元素？最坏元素又如何？
平均：待查找的元素等概率出现（概率为：1/n）：（1 + 2 + 3 + ... + n）/ n = (n+1) / 2
最坏：n
运行时间均为：O(n) - 2.2-4 应如何修改任何一个算法，才能使之具有良好的最好情况运行时间？
在算法中加入对最好情况的判断。例如：排序时，如果输入序列已经排好序，则直接return，这样最好情况运行时间为O（n）。
@TOC
- 2.3-1 说明并归排序在数组A = < 3,41,52,26,38,57,9,49 >上的操作。
- 2.3-2 重写过程MERGE，使之不使用哨兵，而是一旦数组L或R的所有元素均被复制回A就立刻停止，然后把另一个数组的剩余部分赋值回A。
MERG(A,p,q,r):
n1 = q-p+1
n2 = r-q
for i = 1 to n1
L[i] = A[p+i-1]
for j = 1 to n2
R[j] = A[q+j}
temp = 1
for k1 = p to q and k2 = q+1 to r
if L[k1] <= L[k2]
A[temp] = L[k1]
temp = temp + 1
else
A[temp] = L[k2]
temp = temp + 1
while(k1 <= q)
A[temp++] = L[k1++]
while(k2 <= r)
A[temp++] = R[k2++]- 2.3-3使用数学归纳法证明：当n刚好是2的幂时，一下递归式的解是T(n)=nlgn。
T(n)=2，若n=2
T(n)=2T(n/2)+n, 若n=2^k,k>1
- 2.3-4 我们可以把插入排序表示为如下的一个递归过程。为了排序A[1..n]，我们递归地排序A[1..n-1]，然后把A[n]插入已排序的数组A[1..n-1]。为插入排序的这个递归版本的最坏情况运行时间写一个递归式。
- 2.3-5 回顾查找问题(参见练习2.1-3)，注意到，如果序列A已排好序，就可以将该序列的中点与v进行比较。根据比较的结果，原序列中有一半就可以不用再做进一步的考虑了。二分查找算法重复这个过程，每次都将序列剩余部分的规模减半。为二分查找写出迭代或递归的伪代码。证明:二分查找的最坏情况运行时间为O(lgn)。
BINARY_SEARCH(A，key,p.r):
if mid >= r and key != A[p]
return NIL
j = (r-p) / 2
if key = A[j]
return j;
else
if key < A[j]
return BINARY_SEARCH(A,key,p,j)
else
return BINARY_SEARCH(A,key,j,r)
// T(n) = O(lgn)- 2.3-6 注意到2.1节中的过程 INSERTION-SORT 的第5~7行的while循环采用一种线性查找来(反向)扫描已排好序的子数组A[1..j-1]。我们可以使用二分查找(参见练习2.3-5)来把插入排序的最坏情况总运行时间改进到O(nlgn)吗?
INSERTION_SORT:
for i=2 to A.length
key = A[i]
low = 1
high = i-1
while low <= high
mid = (low + high) / 2
if key = A[mid]
break
else if key < A[mid]
high = mid- 1
else
low = mid + 1
for j = mid to i-1
A[j+1] = A[j]
A[mid] = key在最坏情况下，二分查找的时间复杂度为nlgn，但元素的移动次数未改变，它依赖于待排序表的初始状态，因此总运行时间不能改进到O(nlgn)，仍然为O(n^2)。
- 2.3-7 描述一个运行时间为O(nlgn)的算法，给定n个整数的集合S和另一个整数x，该算法能确定S中是否存在两个其和刚好为x的元素。
（1）将集合S排序（并归排序） O(lgn)
（2）循环折半查找 x-A[i]，存在 return true；不存在 return false
CHECK_SUMS(A,x):
SORT(A)
for i = 1 to A.length
if BINARY_SEARCH(A,x-A[i],i,n)
return true@TOC
- 2-1 (在归并排序中对小数组采用插入排序）虽然归并排序的最坏情况运行时间为O(n lgn)，而插人排序的最坏情况运行时间为O(n^2)，但是插入排序中的常量因子可能使得它在n较小时，在许多机器上实际运行得更快。因此，在归并排序中当子问题变得足够小时，采用插人排序来使递归的叶变粗是有意义的。考虑对归并排序的一种修改，其中使用插入排序来排序长度为k的n/k个子表，然后使用标准的合并机制来合并这些子表，这里k是一个待定的值。
**a. 证明:插入排序最坏情况可以在O(nk)时间内排序每个长度为k的n/k个子表。
b. 表明在最坏情况下如何在O(nlg(n/k))时间内合并这些子表。
c. 假定修改后的算法的最坏情况运行时间为O(nk十nlg(n/k))，要使修改后的算法与标准的归并排序具有相同的运行时间，作为n的一个函数，借助O记号，k的最大值是什么?
d. 在实践中，我们应该如何选择k?**a. 插入排序最坏运行时间为O(n^2)，即 ak^2 + bk + c；
n/k个子表共需：n/k(ak^2 + bk + c) = ank + bn + nc/k = O(nk)；b. 并归排序时递归树树高为：lg(n/k)，每个叶子代价为ck
合并的总代价为O(ck(n/k)lgn/k) = O(nlgn/k)c. O(nk + nlgn/k) = O(nlgn)，即k <= lgn，k的最大值为lgn
d. 选择的k值应使插入排序快于并归排序
- **2-4 (逆序对）假设A_1..n]是一个有n个不同数的数组。若i<j且Ai>Aj]，则对偶(i，j)称为A的一个逆序对(inversion)。
a. 列出数组(2，3，8，6，1>的5个逆序对。
b. 由集合{1，2，…，n)中的元素构成的什么数组具有最多的逆序对?它有多少逆序对?
c. 插人排序的运行时间与输人数组中逆序对的数量之间是什么关系?证明你的回答。**a. < 2,1 >,< 3,1 >,< 8,1 >,< 6,1 >,< 8,6 >
b. 当集合降序排列时，具有最多的逆序对，共有n(n-1)/2对。
c. 逆序对的数量决定while内循环的执行次数。
