Problem 1 (教材习题 2.1-3)

考虑以下 查找问题 ：

输入 ： $n$ 个数的一个序列 $A = \langle a_1, a_2, \cdots, a_n\rangle$ 和一个值 $v$ 。

输出 ：下标 $i$ 使得 $v = A[i]$ 或者当 $v$ 不在 $A$ 中出现时， $v$ 为特殊值 $NIL$ 。

写出 线性查找 的伪代码，它扫描整个序列来查找 $v$ 。使用一个循环不变式来证明你的算法是正确的。确保你的循环不变式满足三条必要的性质。

Solution

循环不变式：第1-5行循环的每次迭代开始前，不存在下标 $1 \le j < i$ 使得 $A[j] = v$ 。

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

保持：迭代过程中，算法2-4行检查是否 $A[i] = v$ ，

• 如果是，则返回 $i$ ，我们找到了使得 $v = A[i]$ 的下标 $i$ 并以正确的结果停止了算法。

• 如果不是，在 $A[1], A[2], …, A[i - 1]$ 都不等于 $v$ 的基础上，我们又知道了 $A[i]$ 不等于 $v$ ，于是下一次迭代时，不存在下标 $1 \le j < i + 1$ 使得 $A[j] = v$ ，我们保持了循环不变式。

终止：迭代终止时， $i = n + 1$ ，根据不变式，不存在下标 $1 \le j \le n$ 使得 $A[j] = v$ ，我们正确地返回了 $NIL$ 。

综上，算法1正确。

Problem 2 (教材习题 2.1-4)

考虑把两个 $n$ 位二进制整数加起来的问题，这两个整数分别存储在两个 $n$ 元数组 $A$ 和 $B$ 中。这两个整数的和应该按二进制形式形式存储在一个 $n + 1$ 元的数组 $C$ 中。请给出该问题的形式化描述，并写出伪代码。

Solution

这里默认数组元素从左往右排列，表示数字时左边为高位，右边为低位。如果你和我的方向相反，但是意思一样的话也是可以的。

这个算法的循环不变式是：第2-9行循环的每次迭代开始前，${carry, C[i+2..n+1]} = A[i+1..n] + B[i+1..n]$ ，其中 ${carry, C[i+2..n+1]}$ 表示将 $carry$ 拼接在 $C[i+1]$ 的位置得到的结果。

可以通过这个不变式来证明算法的正确性，这里不再赘述。

Problem 3 (教材习题 2.2-2)

考虑排序存储在数组 $A$ 中的 $n$ 个数：首先找出 $A$ 中的最小元素，并将其与 $A[1]$ 中的元素进行交换。接着，找出 $A$ 中的次最小元素并将其与 $A[2]$ 中的元素进行交换。对 $A$ 中前 $n - 1$ 个元素按该方式继续，该算法称为 选择排序 ，写出其伪代码。该算法维持的循环不变式是什么？为什么它只需要对前 $n - 1$ 个元素，而不是对所有 $n$ 个元素运行？用 $\Theta$ 记号给出选择排序的最好情况与最坏情况运行时间。

Solution

该算法维持的循环不变式是：第1-8行循环的每次迭代开始前，$A[1..i-1]$ 按照从小到大的顺序包含了 $A$ 中前 $i - 1$ 小的元素。(不变式的证明读者可自行完成)

$n - 1$ 此循环结束后，$i = n$ ，由不变式可知， $A[1..n-1]$ 按照从小到大的顺序包含了 $A$ 中前 $n - 1$ 小的元素，于是此时的 $A[n]$ 必定是 $A$ 中最大的元素，因而没必要继续迭代了。

选择排序的最好情况与最坏情况的运行时间都是 $\Theta(n^2)$ 。因为无论在什么情况下，算法第3-8行的循环都会运行 $n - i$ 次以找出剩余元素当中最小的那一个，从而产生了如下的时间代价：

$\sum_{i = 1}^{n-1}(n - i) = n(n - 1) - \sum_{i = 1}^{n-1}i = \frac{n(n-1)}{2} = \Theta(n^2)$

Problem 4 (教材习题 2.2-3)

再次考虑线性查找问题（参见练习1-1问题1）。假定要查找的元素等可能地为数组中的任意元素，平均需要检查输入序列的多少元素？最坏情况又如何呢？用 $\Theta$ 记号给出平均情况和最坏情况的运行时间。证明你的答案。

Solution

本题假设 $v$ 能够在 $A[1..n]$ 中找到。考虑 $P{A[i] = v} = \frac{1}{n}$ ，且当 $A[i] = v$ 时，需要检查输入序列的 $i$ 个元素（前 $i - 1$ 个检查后拒绝，最后第 $i$ 个检查后接受）。记检查次数为 $X$ ，则：

$E(X) = \sum_{i = 1}^{n} i \cdot P{A[i] = v} = \sum_{i = 1}^{n} i \cdot \frac{1}{n} = \frac{n + 1}{2}$

所以平均情况下需要比较 $\frac{n+1}2$ 次。

最坏情况就是只有 $A[n] = v$ 的情况，需要比较 $n$ 次。

因此，平均情况和最坏情况的最坏时间都是 $\Theta(n)$ 。