Problem 1 (教材习题 2.1-3)
考虑以下 查找问题 :
输入 : n 个数的一个序列 A=⟨a1,a2,⋯,an⟩ 和一个值 v 。
输出 :下标 i 使得 v=A[i] 或者当 v 不在 A 中出现时, v 为特殊值 NIL 。
写出 线性查找 的伪代码,它扫描整个序列来查找 v 。使用一个循环不变式来证明你的算法是正确的。确保你的循环不变式满足三条必要的性质。
Solution
循环不变式:第1-5行循环的每次迭代开始前,不存在下标 1≤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≤j<i+1 使得 A[j]=v ,我们保持了循环不变式。
终止:迭代终止时, i=n+1 ,根据不变式,不存在下标 1≤j≤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 个元素运行?用 Θ 记号给出选择排序的最好情况与最坏情况运行时间。
Solution
该算法维持的循环不变式是:第1-8行循环的每次迭代开始前,A[1..i−1] 按照从小到大的顺序包含了 A 中前 i−1 小的元素。(不变式的证明读者可自行完成)
n−1 此循环结束后,i=n ,由不变式可知, A[1..n−1] 按照从小到大的顺序包含了 A 中前 n−1 小的元素,于是此时的 A[n] 必定是 A 中最大的元素,因而没必要继续迭代了。
选择排序的最好情况与最坏情况的运行时间都是 Θ(n2) 。因为无论在什么情况下,算法第3-8行的循环都会运行 n−i 次以找出剩余元素当中最小的那一个,从而产生了如下的时间代价:
i=1∑n−1(n−i)=n(n−1)−i=1∑n−1i=2n(n−1)=Θ(n2)
Problem 4 (教材习题 2.2-3)
再次考虑线性查找问题(参见练习1-1问题1)。假定要查找的元素等可能地为数组中的任意元素,平均需要检查输入序列的多少元素?最坏情况又如何呢?用 Θ 记号给出平均情况和最坏情况的运行时间。证明你的答案。
Solution
本题假设 v 能够在 A[1..n] 中找到。考虑 P{A[i]=v}=n1 ,且当 A[i]=v 时,需要检查输入序列的 i 个元素(前 i−1 个检查后拒绝,最后第 i 个检查后接受)。记检查次数为 X ,则:
E(X)=i=1∑ni⋅P{A[i]=v}=i=1∑ni⋅n1=2n+1
所以平均情况下需要比较 2n+1 次。
最坏情况就是只有 A[n]=v 的情况,需要比较 n 次。
因此,平均情况和最坏情况的最坏时间都是 Θ(n) 。