《算法导论》第二章-思考题（参考答案）

算法导论（第三版）参考答案：思考题2.1，思考题2.2，思考题2.3，思考题2.4

Problem 2-1

(Insertion sort on small arrays in merge sort ) Although merge sort runs in Θ(nlgn) worst-case time and insertion sort runs in Θ(n2) worst-case time, the constant factors in insertion sort can make it faster in practice for small problem sizes on many machines. Thus, it makes sense to coarsen the leaves of the recursion by using insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which n/k sublists of length k are sorted using insertion sort and then merged using the standard merging mechanism, where k is a value to be determined. 1. Show that insertion sort can sort the n/k sublists, each of length k, in Θ(nk) worst-case time. 2. Show how to merge the sublists in Θ(nlg(n/k)) worst-case time. 3. Given that the modified algorithm runs in Θ(nk+nlg(n/k)) worst-case time, what is the largest value of k as a function of n for which the modified algorithm has the same running time as standard merge sort, in terms of Θ -notation? 4. How should we choose k in practice?

第1问：

因为插入排序的最坏渐进时间为 Θ(n2) , 即 ak2+bk+c . 所以对 n/k 个长度为 k 的数组，总的时间为： nk(ak2 bk c)=ank bn cnk=Θ(nk) 第2问：

想象一下归并排序分析用到的递归树。此时叶子节点代价不再是 c ，而是ck，所以递归树高 lg(n/k) 。合并总代价为 cnlg(n/k) ，即最坏渐进时间为 Θ(nlg(n/k)) 。

第3问：

Θ(nk+nlg(n/k))=Θ(nlgn)Θ(k+lg(n/k))=Θ(lgn) 当 k<lgn ，两者渐进时间相同为 Θ(nlgn) 。 k 最大值为lgn

第4问：

选择插入排序比归并排序快的最大数组长度作为 k 值。

Runtime comparison

I’m implemented this in C and in Python. I added selection for completeness sake in the C version. I ran two variants, depending on whether merge() allocates its arrays on the stack or on the heap (stack won’t work for huge arrays). Here are the results:

STACK ALLOCATION ================ merge-sort = 0.173352 mixed-insertion = 0.150485 mixed-selection = 0.165806 HEAP ALLOCATION =============== merge-sort = 1.731111 mixed-insertion = 0.903480 mixed-selection = 1.017437

Here’s the results I got from Python:

merge-sort = 2.6207s mixed-sort = 1.4959s

I can safely conclude that this approach is faster.

C runner output

merge-sort = 0.153748 merge-insertion = 0.064804 merge-selection = 0.069240

Python runner output

merge-sort = 0.1067s mixed-sort = 0.0561s

C code

#include <stdlib.h> #include <string.h> #define INSERTION_SORT_TRESHOLD 20 #define SELECTION_SORT_TRESHOLD 15 void merge(int A[], int p, int q, int r) { int i, j, k; int n1 = q - p 1; int n2 = r - q; #ifdef MERGE_HEAP_ALLOCATION int *L = calloc(n1, sizeof(int)); int *R = calloc(n2, sizeof(int)); #else int L[n1]; int R[n2]; #endif memcpy(L, A p, n1 * sizeof(int)); memcpy(R, A q 1, n2 * sizeof(int)); for(i = 0, j = 0, k = p; k <= r; k ) { if (i == n1) { A[k] = R[j ]; } else if (j == n2) { A[k] = L[i ]; } else if (L[i] <= R[j]) { A[k] = L[i ]; } else { A[k] = R[j ]; } } #ifdef MERGE_HEAP_ALLOCATION free(L); free(R); #endif } void merge_sort(int A[], int p, int r) { if (p < r) { int q = (p r) / 2; merge_sort(A, p, q); merge_sort(A, q 1, r); merge(A, p, q, r); } } void insertion_sort(int A[], int p, int r) { int i, j, key; for (j = p 1; j <= r; j ) { key = A[j]; i = j - 1; while (i >= p && A[i] > key) { A[i 1] = A[i]; i = i - 1; } A[i 1] = key; } } void selection_sort(int A[], int p, int r) { int min, temp; for (int i = p; i < r; i ) { min = i; for (int j = i 1; j <= r; j ) if (A[j] < A[min]) min = j; temp = A[i]; A[i] = A[min]; A[min] = temp; } } void mixed_sort_insertion(int A[], int p, int r) { if (p >= r) return; if (r - p < INSERTION_SORT_TRESHOLD) { insertion_sort(A, p, r); } else { int q = (p r) / 2; mixed_sort_insertion(A, p, q); mixed_sort_insertion(A, q 1, r); merge(A, p, q, r); } } void mixed_sort_selection(int A[], int p, int r) { if (p >= r) return; if (r - p < SELECTION_SORT_TRESHOLD) { selection_sort(A, p, r); } else { int q = (p r) / 2; mixed_sort_selection(A, p, q); mixed_sort_selection(A, q 1, r); merge(A, p, q, r); } }

Python code

from itertools import repeat def insertion_sort(A, p, r): for j in range(p 1, r 1): key = A[j] i = j - 1 while i >= p and A[i] > key: A[i 1] = A[i] i = i - 1 A[i 1] = key def merge(A, p, q, r): n1 = q - p 1 n2 = r - q L = list(repeat(None, n1)) R = list(repeat(None, n2)) for i in range(n1): L[i] = A[p i] for j in range(n2): R[j] = A[q j 1] i = 0 j = 0 for k in range(p, r 1): if i == n1: A[k] = R[j] j = 1 elif j == n2: A[k] = L[i] i = 1 elif L[i] <= R[j]: A[k] = L[i] i = 1 else: A[k] = R[j] j = 1 def merge_sort(A, p, r): if p < r: q = int((p r) / 2) merge_sort(A, p, q) merge_sort(A, q 1, r) merge(A, p, q, r) def mixed_sort(A, p, r): if p >= r: return if r - p < 20: insertion_sort(A, p, r) else: q = int((p r) / 2) mixed_sort(A, p, q) mixed_sort(A, q 1, r) merge(A, p, q, r)

Problem 2-2

(Correctness of bubblesort) Bubblesort is popular, but inefficient, sorting algorithm. It works by repeatedly swapping adjancent elements that are out of order.

BUBBLESORT(A) for i = 1 to A.length - 1 for j = A.length downto i 1 if A[j] < A[j - 1] exchange A[j] with A[j - 1] Let A' denote the output of BUBBLESORT(A). To prove that BUBBLESORT is correct, we need to prove that it terminates and that

>A'[1]≤A'[2]≤⋯≤A'[n]>(2.3)

where n=A.length . In order to show that BUBBLESORT actually sorts, what else do we need to prove?

The next two parts will prove inequality (2.3).

State precisely a loop invariant for the for loop in lines 2-4, and prove that this loop invariant holds. Your proof should use the structure of the loop invariant proof presented in this chapter.Using the termination condition of the loop invariant proved in part (2), state a loop invariant for the for loop in lines 1-4 that will allow you to prove inequality (2.3). Your proof should use the structure of the loop invariant proof presented in this chapter.What is the worst-case running time of bubblesort? How does it compare to the running time of insertion sort?

第1问：

证明BUBBLESORT的正确性，除了证明不等式（2.3），还需要证明 A′ 中的元素全部来自于 A 。

第2问：

**内循环-循环不变式：**for循环每次迭代开始，子数组A[j..A.length]中第 j 个元素是最小的，即A[j]<=A[k],k>j；同时元素 A[j..A.length] 是原来在位置 j 到A.length的元素，但是已经挑选出最小元素的。

初始化： 第一次循环迭代之前（当 j=A.length 时），循环不变式成立。因为此时循环不变式中只有一个元素，也是最小元素。

保持： 假设这次迭代之前，有循环不变式 A[j..A.length] 为真。则再次进入循环体，我们检查 A[j],A[j−1] 的大小，并保持了 j−1 位置为 A[j],A[j−1] 中最小的一个。由于已经有 A[j] 为 A[j..A.length] 中最小的元素了，所以 A[j−1] 也应为 A[j−1..A.length] 中最小的元素。此时子数组 A[j..A.length] 是由原来 A[j..A.length] 中的元素组成的。那么for循环这次迭代增加 j 保持了循环不变式。

终止： 循环终止时，j=i 。也就是 A[i..A.length] 是由原来 A[i..A.length] 元素组成，但已经挑选出最小的元素，且最小元素为 A[i] 。

第3问：

外循环-循环不变式： for循环每次迭代开始， A[1..i−1] 构成已排好序的数组，且剩余子数组 A[i..A.length] 中的元素都大于等于 A[1..i−1] 。

初始化： 第一次迭代前，子数组 A[1..i−1] 为空，循环不变式显然成立。（更好理解的是第二次迭代）

保持： 如果第 i 次迭代前，循环不变式为真，A[1..i−1]为已排序。那么进入循环内，根据内循环-循环不变式性质，子数组 A[i..A.length] 第 i 位置被置最小元素。于是A[1..i]构成新的已排好序的数组，剩余 A[i+1..A.length] 也满足都大于 A[i..A.length] 中元素。迭代保持了循环不变式。

终止： 循环终止， i=A.length 。即 A[1..A.length−1] 都已排序好了，同时剩余的 A[A.length] 比 A[1..A.length−1] 中的元素大。最终整个数组 A[1..A.length] 已排序，不等式（2.3）成立。

第4问：

T(n)=c1n+c2∑2nj+c3∑2n(j−1)+c4∑2n(j−1)=Θ(n2) 最坏情况运行时间和插入排序一样，都是 Θ(n2) 。 但是插入排序最好情况运行时间为 Θ(n) ，冒泡排序则为 Θ(n2) 。我们可以改进冒泡排序，加入判断：是否输入是已排序的数组，若是，就返回数组。

同时，冒泡排序中存在大量地交换，相比于插入操作，会更耗费资源。

Problem 2-3

The following code fragment implements Horner’s rule for evaluating a polynomial

>P(x)=∑k=0nakxk==a0+x(a1+x(a2+⋯+x(an−1+xan)⋯))> given the coefficients a0,a1,…,an and a value for x :

y = 0 for i = n downto 0 y = aᵢ x·y

In terms of Θ-notation, what is the running time of this code fragment for Horner’s rule?

Write pseudocode to implement the naive polynomial-evaluation algorithm that computes each term of the polynomial from scratch. What is the running time of this algorithm? How does it compare to Horner’s rule?

Consider the following loop invariant:

At the start of each iteration of the for loop of lines 2-3,

>>y=∑k=0n−(i+1)ak+i+1xk>> Interpret a summation with no terms as equaling 0. Following the structure of the loop invariant proof presented in this chapter, use this loop invariant to show that, at termination, y=∑k=0nakxk .

Conclude by arguing that the given code fragment correctly evaluates a polynomial characterized by the coefficients a0,a1,…,an .

第1问：

Θ(n) .

第2问：

y = 0 for i = 0 to n m = 1 for k = 1 to i m = m·x y = y + aᵢ·m

运行时间为 Θ(n2) ，比霍纳规则相比，要慢。

第3问：

初始化： i=n,y=0 ，循环不变式为真。

保持：第 i 次迭代，我们有 y=ai x∑k=0n−(i 1)ak i 1xk=aix0 ∑k=0n−i−1ak i 1xk 1=aix0 ∑k=1n−iak ixk=∑k=0n−iak ixk 终止： i=−1 ，

y=∑k=0n−i−1ak+i+1xk=∑k=0nakxk 第4问：

显然由第3问可知，根据循环不变式，终止时 y 值恰好为所求多项式。

Problem 2-4

Let A[1..n] be an array of n distinct numbers. If i<j and A[i]>A[j] , then the pair (i,j) is called an inversion of A .

List the five inversions in the array ⟨2,3,8,6,1⟩.

What array with elements from the set 1,2,…,n has the most inversions? How many does it have?What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.Give an algorithm that determines the number of inversions in any permutation of n elements in Θ(nlgn) worst-case time. (Hint: Modify merge sort).

第1问：

<2,1>,<3,1>,<8,1>,<8,6>,<6,1> <script type="math/tex" id="MathJax-Element-100"><2,1>,<3,1>,<8,1>,<8,6>,<6,1></script>

第2问：

将数组反向排序： ⟨n,n−1,…,1⟩ ，有 (n−1)+(n−2)+⋯+1=n(n−1)2 对逆序对。

第3问：

逆序对的数量，影响插入排序while循环内的执行次数。也就是有多少逆序对，就要执行多少次内循环。所以，含有逆序对的数组排序时间为 Θ(n+d) ，其中 d 为数组中含有逆序对的数量。

第4问：

思路：归并过程中，找出L堆元素大于 R <script type="math/tex" id="MathJax-Element-106">R</script>堆元素的个数与逆序对数量间的关系。

第一种方法：

MERGE(A, p, q, r) n1 = q - p + 1 n2 = r - q let L[1..n1+1]and R[1..n2+1]be new arrays for i = 1 to n1 L[i] = A[p + i -1] for j = 1 to n2 R[j] = A[q + j] L[n1 + 1] = ∞ R[n2 + 1] = ∞ i = 1 j = 1 inversion_num = 0 for k = p to r if L[i] <= R[j] A[k] = L[i] i = i + 1 else inversion_num += n1 + 1 - i A[k] = R[j] j = j + 1 return inversion_num MERGE-SORT(A, p, r) if p < r q = [(p+r)/2] //向下取整 inversion_num = 0 inversion_num += MERGE-SORT(A, p, q) inversion_num += MERGE-SORT(A, q+1, r) inversion_num += MERGE(A, p, q, r) return inversion_num else return 0

第二种方法：

MERGE(A, p, q, r) n1 = q - p + 1 n2 = r - q let L[1..n1+1]and R[1..n2+1]be new arrays for i = 1 to n1 L[i] = A[p + i -1] for j = 1 to n2 R[j] = A[q + j] L[n1 + 1] = ∞ R[n2 + 1] = ∞ i = 1 j = 1 inversion_num = 0 count = 0 for k = p to r if L[i] <= R[j] inversion_num += count A[k] = L[i] i = i + 1 else count = count + 1 A[k] = R[j] j = j + 1 return inversion_num MERGE-SORT(A, p, r) if p < r q = [(p+r)/2] //向下取整 inversion_num = 0 inversion_num += MERGE-SORT(A, p, q) inversion_num += MERGE-SORT(A, q+1, r) inversion_num += MERGE(A, p, q, r) return inversion_num else return 0

C code

#include <stdio.h> int merge(int A[], int p, int q, int r) { int i, j, k, inversion_num = 0; int n1 = q - p + 1; int n2 = r - q; int L[n1]; int R[n2]; for (i = 0; i < n1; i++) L[i] = A[p + i]; for (j = 0; j < n2; j++) R[j] = A[q + j + 1]; for(i = j = 0, k = p; k <= r; k++) { if (L[i] <= R[j]) { A[k] = L[i++]; } else { A[k] = R[j++]; inversion_num += n1 - i; } } return inversion_num; } int merge_sort(int A[], int p, int r) { if (p < r) { int inversion_num = 0; int q = (p + r) / 2; inversion_num += merge_sort(A, p, q); inversion_num += merge_sort(A, q + 1, r); inversion_num += merge(A, p, q, r); return inversion_num; } else { return 0; } }