Problem 2-1

2-1 Insertion sort on small arrays in merge sort

Although merge sort runs in $\Theta (n \lg n)$ worst-case time and insertion sort runsin $\Theta (n^2)$ worst-case time, the constant factors in insertion sort can make it fasterin 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 inwhich $\frac{n}{k}$ sublists of length $k$ are sorted using insertion sort and then mergedusing the standard merging mechanism, where $k$ is a value to be determined.

a. Show that insertion sort can sort the $\frac{n}{k}$ sublists, each of length $k$ , in $\Theta (nk)$ worst-case time.

b. Show how to merge the sublists in $\Theta (n \lg (\frac{n}{k}))$ worst-case time.

c. Given that the modified algorithm runs in $\Theta (nk + n \lg \frac{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 $\Theta$ -notation?

d. How should we choose kk in practice?

a. 证明：插入排序最坏情况可以在 $\Theta (nk)$ 时间内排序每个长度为 $k$ 的 $\frac{n}{k}$ 个子表。

插入排序的渐进时间复杂度为 $\Theta (n^2)$ ，也即 $an^2 + bn +c$ 。所以对于 $\frac{n}{k}$ 个长度为 $k$ 的数组，总代价为：

$\frac{n}{k} (ak^2 + bk + c) = ank + bn + \frac{cn}{k} = \Theta (nk)$

b. 表明在最坏情况下如何在 $\Theta (n \lg (\frac{n}{k}))$ 时间内合并这些子表。

此时，递归树高为 $\lg \frac{n}{k} + 1$ ，除最后一层外其余层的代价为 $cn$ ；最后一层代价为 $ank + bn + \frac{cn}{k}$ 。故，合并子表的总代价为：

$cn \lg \frac{n}{k} = \Theta (n \lg \frac{n}{k})$

c. 假定修改后的算法的最坏情况运行时间为 $\Theta (nk + n \lg \frac{n}{k})$ ，要使修改后的算法与标准的归并排序具有相同的运行时间，作为 $n$ 的一个函数，借助 $\Theta$ 符号， $k$ 的最大值是什么？

$\Theta (nk + n\lg \frac{n}{k}) = \Theta (n \lg n)$

$\Theta (k + \lg \frac{n}{k}) = \Theta (\lg n)$

故 $k < \lg n$ ；当 $k = \lg n$ 时， $\lg \frac{n}{k}$ 相对 $\lg n$ 被忽略；故 $k$ 的最大值为 $\lg n$ 。

d. 在实践中，我们应该如何选择 $k$ ？

选择插入排序比合并排序快的最大列表长度。

C Code

#include <stdio.h>

#include <stdlib.h>

void subInsertionSort(int *array, unsigned p, unsigned q) {

if (p >= q) return;

int temp, i, key;

for (p = p + 1; p <= q; p++) {

temp = array[p];

for (i = p - 1; i >= 0; i--) {

key = array[i];

if (temp >= key) {

break;

}

array[i + 1] = key;

array[i] = temp;

}

}

}

void mergeArray(int *array, unsigned p, unsigned q, unsigned r) {

if (p > q || q >= r) return;

unsigned n1 = q - p + 1;

unsigned n2 = r - q;

int length = sizeof(int);

int *left = malloc(length * (n1 + 1));

int *right = malloc(length * (n2 + 1));

for (unsigned i = 0; i < n1; i++) {

left[i] = array[p + i];

}

for (unsigned i = 0; i < n2; i++) {

right[i] = array[q + i + 1];

}

left[n1] = right[n2] = UINT16_MAX;

unsigned i = 0, j = 0; for (; p <= r; p++) {

if (left[i] <= right[j]) {

array[p] = left[i++];

}

else {

array[p] = right[j++];

}

}

}

/**

Merge sort 归并排序。但对小于 min 的数组采用归并排序。

@param array 数组指针

@param p 数组开始排序的下标（含）

@param r 数组结束排序的下标（含）

@param min 要进行插入排序的长度上限

*/

void mergeSort_subInsertion(int *array, unsigned p, unsigned r, unsigned min) {

if (p > r) return;

if (r - p < min) {

subInsertionSort(array, p, r);

return;

}

unsigned q = (p + r) / 2;

mergeSort_subInsertion(array, p, q, min);

mergeSort_subInsertion(array, q + 1, r, min);

mergeArray(array, p, q, r);

}

Problem 2-2

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)

1    for i = 1 to A.length - 1

2        for j = A.length downto i + 1

3            if A[j] < A[j - 1]

4                exchange A[j] with A[j - 1]

a. 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.lengthn=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).

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

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

d. What is the worst-case running time of bubblesort? How does it compare to the running time of insertion sort?

a. 假设 A` 标识 BUBBLESORT(A) 的输出。为了证明 BUBBLESORT 正确，我们必须证明他将终止并且有：

A′[1] ≤ A′[2] ≤ ⋯ ≤A′[n] (2.3)

其中 n = A.length。为了证明 BUBBLESORT 确实完成了排序，我们还需要证明什么？

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

b. 为第 2~4 行的 for 循环精确地说明一个循环不变式，并证明该循环不变式成立。你的证明应该使用本章中给出的循环不变式证明的结构。

内循环-循环不变式：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 - 1..A.length] 是由原来 A[j - 1..A.length] 中的元素组成的。那么 for 循环这次迭代增加位于 j - 1 的元素保持了循环不变式。

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

c. 使用（b）部分证明的循环不变式的终止条件，为第 1~4 行的 for 循环说明一个循环不变式，该不变式将使你能证明不等式（2.3）。你的证明应该适用本章中给出的循环不变式证明的结构。

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

初始化：第一次循环迭代之前（当 i = 1 时），此时数组 A[1..i - 1] 为空数组，故循环不变式成立。

保持：假设第 i 次迭代之前，循环不变式成立，即 A[1..i−1] 已排好序，且剩余子数组 A[i..A.lenght] 中的元素都大于等于 A[i - 1]。则再次进入循环体，根据 b 可得，A[i..A.length] 是由原来 A[i..A.length] 元素组成，但已经挑选出最小的元素，且最小元素为 A[i]。故 A[1..i] 也已升序排好，且 A[i + 1..A.length] 中的元素均大于 A[i]。

终止：循环终止时，i = A.length - 1。也就是 A[1..A.length - 1] 已升序，且 A[A.length] 大于 A[1..A.length - 1] 中的任意一个元素；所以 A[1..A.length] 已排好升序。

d. 冒泡排序的最坏情况运行时间是多少？与插入排序的运行时间相比，其性能如何？

$T(n) = c_{1} n + c_{2} \sum_{j = 1}^{n - 1}(n - j) + c_{3} \sum_{j = 1}^{n - 1} (n - j - 1) + c_{4} \sum_{j = 1}^{n - 1} (n - j - 1) = \Theta (n^2)$

最坏情况运行时间和插入排序一样，都是 $\Theta(n^2)$ 。

但是插入排序最好情况运行时间为 $\Theta(n)$ ，即只执行 n - 1 次比较；冒泡排序的比较次数则没有减少，故时间复杂度仍为 $\Theta(n^2)$ 。

同时，若使用数组数据结构，则冒泡排序与插入排序的交换操作数量一致，均为逆序对数；但若使用链表数据结构的话，其交换操作会比插入操作数量多很多。

故，冒泡排序所需的平均运行时间比插入排序多的多。

C Code

/**

冒泡排序

@param array 数组

@param length 数组长度

*/

void bubbleSort(int *array, int length) {

unsigned i = 0, j, temp;

for (; i < length - 1; i++) {

for (j = length - 1; j > i; j--) {

if (array[j] < array[j - 1]) {

temp = array[j];

array[j] = array[j - 1];

array[j - 1] = temp;

}

}

}

}

Problem 2-3

2-3 Correctness of Horner’s rule

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

$P(x) = \sum_{k=0}^n a_{k} x^k = a_{0} + x(a_{1} + x(a_{2} + ⋯ + x(a_{n - 1} + x a_{n})⋯))$

given the coefficients $a_{0}, a_{1}, ..., a_{n}$ and a value for x:

1 y = 0

2 for i = n downto 0

3   y = $a_{i}$ + x * y

a. In terms of $\Theta$ -notation, what is the running time of this code fragment forHorner’s rule?

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

c. Consider the following loop invariant:

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

       $y = \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1} x^k.$

    Interpret a summation with no terms as equaling 0. Following the structure ofthe loop invariant proof presented in this chapter, use this loop invariant to showthat, at termination,

     $y = \sum_{k=0}^{n - (i + 1)} a_{k + i + 1} x^k.$

d. Conclude by arguing that the given code fragment correctly evaluates a poly-nomial characterized by the coefficients $a_{0}, a_{1}, ..., a_{n}$ .

a. 借助 $\Theta$ 记号，实现霍纳规则的以上代码片段的运行时间是多少？

$c_{1} + c_{2} (n + 1) + c_{3} n = \Theta(n)$

b. 编写伪代码来实现朴素的多项式求值算法，该算法从头开始计算多项式的每个项。该算法的运行时间是多少？与霍纳规则相比，其性能如何？

1 y = 0

2 for i = 0 to n

3 m = 1

4 for k = 1 to i

5 m = m * x

6 y = y + $a_{i}$ * m

运行时间为： $c_{1} + c_{2} (n + 1) + c_{3} n + c_{4} n i + c_{5} n (i - 1) + c_{6} n = \Theta(n^2)$ 。比霍纳规则相比要慢。

可以优化一下：

1 y = 0

2 m = 1

3 for i = 0 to n

4 y = y + $a_{i}$ * m

5 m = m * x

$c_{1} + c_{2} + c_{3} (n + 1) + (c_{4} + c_{5}) n = \Theta(n)$ 。与霍纳规则相同。

c. 考虑一下循环不变式：

在第 2~3 行 for 循环每次迭代的开始有

$y = \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1} x^k$

把没有项的和式解释为等于 0。遵照本章中给出的循环不变式证明的结构，使用该循环不变式来证明终止时有 $y = \sum_{k=0}^{n - (i + 1)} a_{k + i + 1} x^k.$

初始化：在第一次迭代之前， i = n，y = 0，满足条件。

保持：第 i 次迭代， $y = a_{i} + x \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1} x^k = a_{i} x^0 + \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1} x^{k + 1} = a_{i} x^0 + \sum_{k = 1}^{n - i} a_{k + i} x^k = \sum_{k = 0}^{n - i} a_{k + i} x^k$ 。

终止：i = -1，则 $y = \sum_{k = 0}^{n - (-1 + 1)} a_{k - 1 + 1} x^k. = \sum_{k = 0}^{n} a_{k} x^k$ ，满足题意。

d. 最后证明上面给出的代码片段将正确地求由系数 $a_{0}, a_{1}, ..., a_{n}$ 刻画的多项式的值。

可根据 c 中循环不变式的终止段，得出该结论。

Problem 2-4

2-4 Inversions

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.

a. List the five inversions of the array {2, 3, 8, 6, 1}.

b. What array with elements from the set {1, 2, ..., n} has the most inversions? How many does it have?

c. What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.

d. Give an algorithm that determines the number of inversions in any permutation on n elements in $\Theta(n \lg n)$ worst-case time. (Hint: Modify merge sort.)

a. 列出数组{2, 3, 8, 6, 1} 的 5 个逆序对。

{2, 1}, {3, 1}, {8, 6}, {8, 1}, {6, 1}

b. 由集合 {1, 2, ..., n} 中的元素构成的什么数组具有最多的逆序对？它有多少逆序对？

降序集合 {n, n - 1, ..., 1} 具有最多的逆序对。逆序对数量： $\sum_{k = n - 1}^1 k = \frac{(n - 1 + 1)(n - 1)}{2} = \frac{n (n - 1)}{2}$ 。

c. 插入排序的运行时间与输入数组中逆序对的数量之间是什么关系？证明你的回答。

逆序对数量即为 while 循环内的交换操作数量。也就是有多少个逆序对，就要执行多少次 while 内循环。所以，含有逆序对的数组排序时间为 $\Theta(n + d)$ ，其中 d 为数组中含有逆序对的数量。

d. 给出一个确定在 n 个元素的任何排列中逆序对数量的算法，最坏情况需要 $\Theta(n \lg n)$ 事件。（提示：修改归并排序）

C Code

/**

对子数组 A[p, q] 和 A[q + 1, r] 做归并排序。p、q、r 为数组下标，且满足 p <= q < r。

@param array 数组指针

@return 逆序对数量

*/

unsigned mergeReturnInversionNumber(int *array, unsigned p, unsigned q, unsigned r) {

unsigned inversionNumber = 0;

if (q < p || r <= q) {

return inversionNumber;

}

unsigned n1 = q - p + 1;

unsigned n2 = r - q;

size_t length = sizeof(int);

int *L = malloc((n1 + 1) * length);

int *R = malloc((n2 + 1) * length);

for (int i = 0; i < n1; i++) {

L[i] = array[p + i];

}

for (int i = 0; i < n2; i++) {

R[i] = array[q + 1 + i];

}

L[n1] = R[n2] = UINT16_MAX;

int i = 0, j = 0;

for (int k = p; k <= r; k++) {

if (L[i] <= R[j]) {

array[k] = L[i++];

}

else {

array[k] = R[j++];

inversionNumber += n1 - i;

}

}

free(L);

free(R);

return inversionNumber;

}

/**

归并排序对子数组 A[p, q] 和 A[q + 1, r] 做归并排序。p、q、r 为数组下标，且满足 p <= q < r。

@param array 数组指针

@return 逆序对数量

*/

unsigned mergeSortReturnInversionNumber(int *array, unsigned p, unsigned r) {

unsigned inversionNumber = 0;

if (p < r) {

unsigned q = (p + r) / 2;

inversionNumber += mergeSortReturnInversionNumber(array, p, q);

inversionNumber += mergeSortReturnInversionNumber(array, q + 1, r);

inversionNumber += mergeReturnInversionNumber(array, p, q, r);

}

return inversionNumber;

}

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

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

Problem 2-1

a. 证明：插入排序最坏情况可以在 $\Theta (nk)$ 时间内排序每个长度为 $k$ 的 $\frac{n}{k}$ 个子表。

b. 表明在最坏情况下如何在 $\Theta (n \lg (\frac{n}{k}))$ 时间内合并这些子表。

c. 假定修改后的算法的最坏情况运行时间为 $\Theta (nk + n \lg \frac{n}{k})$ ，要使修改后的算法与标准的归并排序具有相同的运行时间，作为 $n$ 的一个函数，借助 $\Theta$ 符号， $k$ 的最大值是什么？

d. 在实践中，我们应该如何选择 $k$ ？

C Code

Problem 2-2

a. 假设 A` 标识 BUBBLESORT(A) 的输出。为了证明 BUBBLESORT 正确，我们必须证明他将终止并且有：

A′[1] ≤ A′[2] ≤ ⋯ ≤A′[n] (2.3)

其中 n = A.length。为了证明 BUBBLESORT 确实完成了排序，我们还需要证明什么？

b. 为第 2~4 行的 for 循环精确地说明一个循环不变式，并证明该循环不变式成立。你的证明应该使用本章中给出的循环不变式证明的结构。

c. 使用（b）部分证明的循环不变式的终止条件，为第 1~4 行的 for 循环说明一个循环不变式，该不变式将使你能证明不等式（2.3）。你的证明应该适用本章中给出的循环不变式证明的结构。

d. 冒泡排序的最坏情况运行时间是多少？与插入排序的运行时间相比，其性能如何？

C Code

Problem 2-3

a. 借助 $\Theta$ 记号，实现霍纳规则的以上代码片段的运行时间是多少？

b. 编写伪代码来实现朴素的多项式求值算法，该算法从头开始计算多项式的每个项。该算法的运行时间是多少？与霍纳规则相比，其性能如何？

c. 考虑一下循环不变式：

在第 2~3 行 for 循环每次迭代的开始有

把没有项的和式解释为等于 0。遵照本章中给出的循环不变式证明的结构，使用该循环不变式来证明终止时有 $y = \sum_{k=0}^{n - (i + 1)} a_{k + i + 1} x^k.$

d. 最后证明上面给出的代码片段将正确地求由系数 $a_{0}, a_{1}, ..., a_{n}$ 刻画的多项式的值。

Problem 2-4

a. 列出数组{2, 3, 8, 6, 1} 的 5 个逆序对。

b. 由集合 {1, 2, ..., n} 中的元素构成的什么数组具有最多的逆序对？它有多少逆序对？

c. 插入排序的运行时间与输入数组中逆序对的数量之间是什么关系？证明你的回答。

d. 给出一个确定在 n 个元素的任何排列中逆序对数量的算法，最坏情况需要 $\Theta(n \lg n)$ 事件。（提示：修改归并排序）

C Code

友情链接更多精彩内容

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

Problem 2-1

a. 证明：插入排序最坏情况可以在 时间内排序每个长度为 的 个子表。

b. 表明在最坏情况下如何在 时间内合并这些子表。

c. 假定修改后的算法的最坏情况运行时间为 ，要使修改后的算法与标准的归并排序具有相同的运行时间，作为 的一个函数，借助 符号， 的最大值是什么？

d. 在实践中，我们应该如何选择 ？

C Code

Problem 2-2

a. 假设 A` 标识 BUBBLESORT(A) 的输出。为了证明 BUBBLESORT 正确，我们必须证明他将终止并且有：

A′[1] ≤ A′[2] ≤ ⋯ ≤A′[n] (2.3)

其中 n = A.length。为了证明 BUBBLESORT 确实完成了排序，我们还需要证明什么？

b. 为第 2~4 行的 for 循环精确地说明一个循环不变式，并证明该循环不变式成立。你的证明应该使用本章中给出的循环不变式证明的结构。

c. 使用（b）部分证明的循环不变式的终止条件，为第 1~4 行的 for 循环说明一个循环不变式，该不变式将使你能证明不等式（2.3）。你的证明应该适用本章中给出的循环不变式证明的结构。

d. 冒泡排序的最坏情况运行时间是多少？与插入排序的运行时间相比，其性能如何？

C Code

Problem 2-3

a. 借助 记号，实现霍纳规则的以上代码片段的运行时间是多少？

b. 编写伪代码来实现朴素的多项式求值算法，该算法从头开始计算多项式的每个项。该算法的运行时间是多少？与霍纳规则相比，其性能如何？

c. 考虑一下循环不变式：

在第 2~3 行 for 循环每次迭代的开始有

把没有项的和式解释为等于 0。遵照本章中给出的循环不变式证明的结构，使用该循环不变式来证明终止时有

d. 最后证明上面给出的代码片段将正确地求由系数 刻画的多项式的值。

Problem 2-4

a. 列出数组{2, 3, 8, 6, 1} 的 5 个逆序对。

b. 由集合 {1, 2, ..., n} 中的元素构成的什么数组具有最多的逆序对？它有多少逆序对？

c. 插入排序的运行时间与输入数组中逆序对的数量之间是什么关系？证明你的回答。

d. 给出一个确定在 n 个元素的任何排列中逆序对数量的算法，最坏情况需要 事件。（提示：修改归并排序）

C Code

友情链接更多精彩内容

a. 证明：插入排序最坏情况可以在 $\Theta (nk)$ 时间内排序每个长度为 $k$ 的 $\frac{n}{k}$ 个子表。

b. 表明在最坏情况下如何在 $\Theta (n \lg (\frac{n}{k}))$ 时间内合并这些子表。

c. 假定修改后的算法的最坏情况运行时间为 $\Theta (nk + n \lg \frac{n}{k})$ ，要使修改后的算法与标准的归并排序具有相同的运行时间，作为 $n$ 的一个函数，借助 $\Theta$ 符号， $k$ 的最大值是什么？

d. 在实践中，我们应该如何选择 $k$ ？

a. 借助 $\Theta$ 记号，实现霍纳规则的以上代码片段的运行时间是多少？

把没有项的和式解释为等于 0。遵照本章中给出的循环不变式证明的结构，使用该循环不变式来证明终止时有 $y = \sum_{k=0}^{n - (i + 1)} a_{k + i + 1} x^k.$

d. 最后证明上面给出的代码片段将正确地求由系数 $a_{0}, a_{1}, ..., a_{n}$ 刻画的多项式的值。

d. 给出一个确定在 n 个元素的任何排列中逆序对数量的算法，最坏情况需要 $\Theta(n \lg n)$ 事件。（提示：修改归并排序）