Problem 1 (教材习题 2-1)

（在归并排序中对小数组采用插入排序） 虽然归并排序的最坏情况运行时间为 $\Theta(n\log n)$ ，而插入排序的最坏情况运行时间为 $\Theta(n^2)$ ，但是插入排序中的常量因子可能使得它在 $n$ 较小时，在许多机器上实际运行得更快。因此，在归并排序中，当子问题变得足够小时，采用插入排序来使递归的叶 变粗 是有意义的。考虑对归并排序的一种修改，其中使用插入排序来排序排序长度为 $k$ 的 $n / k$ 个子表，然后使用标准的合并机制来合并这些字表，这里 $k$ 是一个待定的值。

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

2. 表明在最坏情况下如何在 $\Theta(n\log(n/k))$ 时间内合并这些子表。

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

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

Solution

1. 插入排序一个长度为 $k$ 的子表的时间是 $\Theta(k^2)$ ，一共有 $n / k$ 个子表，总时间是 $\Theta(\frac{n}{k}\cdot k^2) = \Theta(nk)$ 。

2. 考虑第1讲PPT第36页（对应课本2.3.2节）的递归树，由于在子序列长度为 $k$ 的时候开始不用归并排序，而改用插入排序，因此递归树的深度为 $(\log n + 1) - (\log k + 1) = \log(n/k)$ ，每层的合并代价依旧是 $\Theta(n)$ ，从而总合并代价为 $\Theta(n\log(n/k))$ 。

3. $\Theta(nk + n\log(n/k)) = \Theta(n(\log n + k - \log k)) = \Theta(n(\log n + k))$ 。

   • 如果 $k$ 是 $n$ 的函数：

     • 只要 $k(n) = O(\log n)$ ，则 $\Theta(n(\log n + k)) = \Theta(n\log n)$ ，该算法和归并排序具有一样的复杂度；

     • 否则，$k(n) = \omega(\log n)$ ，则 $\Theta(n(\log n + k)) = \Theta(nk)$ ，比原来更慢了。

   • 如果 $k$ 是一个和 $n$ 无关的常数，那么 $\Theta(n(\log n + k)) = \Theta(n\log n)$ ，该算法和归并排序具有一样的渐近复杂度。

因此，从渐近亿以上来看，本题的做法并不能从根本上改进归并排序的时间，只能在数据规模较小的时候凭借系数上的优势获得更快的运行效果。

4. 实际情况中，我们常常是通过选取不同的 $k$ 来进行测试，选择表现性能最好的 $k$ 。不过，如果假设 $k$ 是常数的话，且设总体代价为 $c_1nk + c_2n\log(n/k)$ 的话，你也可以通过对 $k$ 求导求极值点的方式来得到一个最优的常数 $k$ 。

Problem 2 (教材习题 2-2)

（冒泡排序的正确性） 冒泡排序是一种流行但低效的排序算法，它的作用是反复交换相邻的未按次序排列的元素。

1. 假设 $A'$ 表示 $Bubble-Sort(A)$ 的输出。为了证明 $Bubble-Sort(A)$ 正确，我们必须证明它将终止并且有：

$A'[1] \le A'[2] \le … \le A'[n]$

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

下面两部分将证明上述不等式。

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

3. 使用第2问证明的循环不变式的终止条件，为第1-7行的 for 循环说明一个循环不变式，并证明该循环不变式成立；该不变式将使你能证明第1问中提出的不等式。你的证明应该使用第一讲中给出的循环不变式的证明结构。

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

Solution

1. 我们还需要证明 $A'$ 中的元素依旧是原本 $A$ 中的元素。而这一点是显然的，因为我们只是交换了原数组中的元素而已，所以最终得到的数组只是原数组的一个重新排列，自然依旧是原本的元素。

2. 第2-6行 for 循环的不变式：每次迭代开始前，$A[j..n]$ 中的最小元素为 $A[j]$ 。

   • 初始化：第一次迭代开始前， $j = n$ ，不变式显然成立。

   • 保持：若迭代开始前， $A[j..n]$ 中的最小元素为 $A[j]$ ，

     • 如果 $A[j - 1] <= A[j]$ ，那么 $A[j - 1]$ 就是 $A[j - 1..n]$ 中最小的元素；

     • 如果 $A[j - 1] > A[j]$ ，那么算法第4行会交换 $A[j - 1]$ 和 $A[j]$ 中的元素，于是 $A[j -1]$ 就变成了 $A[j - 1..n]$ 中最小的元素。

     则下一次迭代开始前， $A[j-1..n]$ 中的最小元素为 $A[j-1]$ 。

   • 终止：最后一次迭代结束后， $j = i$ ，根据循环不变式，有 $A[i]$ 是 $A[i..n]$ 中的最小元素。

3. 第1-7行 for 循环的不变式：每次迭代开始前，$A[1..i - 1]$ 是 $A[1..n]$ 中前 $i - 1$ 小的元素从小到大排列。

   • 初始化：第一次迭代开始前， $i = 1$ ，不变式显然成立。

   • 保持：若迭代开始前，$A[1..i-1]$ 是 $A[1..n]$ 中前 $i - 1$ 小的元素从小到大排列，由第2-6行 for 循环的不变式可知，算法第2-6行会使得 $A[i]$ 是 $A[i..n]$ 最小的元素，从而在下一次迭代开始前 $A[1..i]$ 是 $A[1..n]$ 中前 $i$ 小的元素从小到大排列。

   • 终止：最后一次迭代结束后，$i = n$ ，根据循环不变式，有 $A[1..n-1]$ 是 $A[1..n]$ 中前 $n - 1$ 小的元素从小到大排列，于是 $A[n]$ 必然是 $A[1..n]$ 中的最大元素。

   于是，$A[1..n]$ 已经排好了序，第1问不等式得证。

4. 第 $i$ 次外层循环会导致内层循环运行 $n - i$ 次，总次数为 $\sum\limits_{i = 1}^{n - 1}(n - i) = \Theta(n^2)$ ，最坏和最好情况下都是如此。因此，在最坏情况下，冒泡排序和插入排序性能相当；在最好情况下，冒泡排序比插入排序慢。

Problem 3 (教材习题 2-3)

（霍纳(Horner)规则的正确性） 给定系数 $a_0, a_1, …, a_n$ 和 $x$ 的值，代码片段

实现了用于求值多项式

$P(x) = \sum_{k = 0}^{n} a_kx^k = a_0 + x(a_1 + x(a_2 + \cdots + x(a_{n-1} + xa_n)\cdots))$

的霍纳规则。

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

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

3. 考虑以下循环不变式：

在第2-4行 for 循环每次迭代的开始有

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

把没有项的和式解释为等于 $0$ 。遵照第1讲中给出的循环不变式证明的结构，使用该循环不变式来证明终止时有 $y = \sum\limits_{k = 0}^{n}a_kx^k$ 。

4. 最后证明上面给出的代码片段将正确地求由系数 $a_0, a_1, …, a_n$ 刻画的多项式的值。

Solution

1. 假设算术运算是常数项时间，由于第2-4行循环运行了 $n + 1$ 次，则整体运行时间为 $\Theta(n)$ 。

2. 伪代码如下，运行时间依旧是 $\Theta(n)$ ，和霍纳规则性能相当。

我上面的算法已经做了一些优化，借助上一个循环中 $x^i$ 的值来计算下一个循环中 $x^{i+1}$ 的值。如果你实现的算法更加暴力，每次都从头计算 $x^i$ 的值的话，那么你的算法时间复杂度应该是 $\Theta(n^2)$ ，性能劣于霍纳规则。

3. 证明：

   • 初始化：第一次迭代开始前， $i = n, y = 0$ ，不变式显然成立。

   • 保持：若迭代开始前， $y = \sum\limits_{k = 0}^{n - (i + 1)} a_{k + i + 1} x^{k}$ ，则算法第3行使得 $y = a_i + x \cdot \sum\limits_{k = 0}^{n - (i + 1)} a_{k + i + 1} x^{k} = \sum\limits_{k = 0}^{n - i} a_{k + i}x^k$ ，保持了不变式。

   • 终止：最后一次迭代结束后， $i = -1$ ，根据循环不变式，有 $y = \sum\limits_{k = 0}^{n}a_kx^k$ 。

4. 由第3问结论可知： $y = \sum\limits_{k = 0}^{n}a_kx^k = P(x)$ ，算法正确地求出了由系数 $a_0, a_1, …, a_n$ 刻画的多项式的值。

Problem 4 (教材习题 2-4)

（逆序对） 假设 $A[1..n]$ 是一个有 $n$ 个不同数的数组。若 $i < j$ 且 $A[i] > A[j]$ ，则二元组 $(i, j)$ 称为 $A$ 的一个 逆序对(inversion) 。

1. 列出数组 $\langle2, 3, 8, 6, 1\rangle$ 的 $5$ 个逆序对。

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

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

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

Solution

1. $(2, 1), (3, 1), (8, 6), (8, 1), (6, 1)$ 。

这里为了方便起见，用元素而不是下标表示。

2. 具有最多逆序对的数组是： $\langle n, n - 1, …, 2, 1\rangle$ ，任意两个元素都是逆序对，一共有 $C_n^2 = \frac{n(n-1)}2$ 个逆序对。

3. 考虑插入排序算法（见第1讲PPT第9页，教材2.1节）第6行的拷贝操作为关键操作，以其操作时间作为算法的运行时间，则插入排序算法的时间是数组中逆序对数量的常数倍。

   • 令 $I(j) = |{i | 1 \le i < j \le n \wedge A[i] > A[j]}|$ ，则数组中逆序对的总数量为 $\sum\limits_{i = 1}^{n} I(i) = \sum\limits_{i = 2}^{n} I(i)$ ，不难发现 $I(1) = 0$ 。

   • 考虑算法第5到第7行的 while 循环会对于每一个 $i < j$ 但是 $A[i] > A[j]$ 的 $i$ 都运行一次（因为 $A[1..j - 1]$ 已经排好序了），一共运行了 $I[j]$ 次。

   • 再考虑第1行到第8行的 for 循环对于 $i$ 从 $2$ 到 $n$ 都运行了一次。

   • 于是，一共需要进行 $\sum\limits_{i = 2}^{n} I(i) = \sum\limits_{i = 1}^{n} I(i)$ 次拷贝操作，恰好是数组中逆序对的数量。假设每次拷贝操作的时间为常数，则总时间为数组中逆序对数量的常数倍。

4. 算法伪代码如下：

该算法的核心思路是分而治之，先递归地计数左半边和右半边的逆序对，然后再借助前后都已经排好序的性质来计数跨越中点的逆序对（关键：算法第34行）。

上述算法只在归并排序原本算法之外添加了常数项时间的操作，因此该算法最坏情况依旧只需要 $\Theta(n\log n)$ 的时间。

这里补充一下逆序对计数问题的洛谷模版题链接，读者可以自行编程并提交评测。

注意数据规模，后10个测试样例数据较大，结果需要用64位整数来存，32位整数会溢出，导致WA。