算法导论9.2 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 2 分钟

9.2-1

这题的证明思路是，只要调用程序RANDOMIZED-SELECT时，\(i\)满足\(1\le i\le r-p+1\)，那么在接下来的递归调用步骤中这个性质恒成立。由于\(i\ge 1\)恒成立，因此在递归调用的过程中，不可能产生\(p>r\)的情况。

接下来证明\(i\ge 1\)恒成立。第8行代码的递归调用没有对\(i\)进行改变，因此原结论成立；第9行代码的递归调用对应的是情况\(i>k\)时的情况，因此\(i-k>0\)，此时的递归调用仍然保持性质成立。故原结论成立。

接下来证明\(i\le r-p+1\)恒成立。第7行代码和第4行的代码混合消去\(k\)后，得到\(i< q-p+1\)，也就是\(i\le q-p\)，可以写成\(i\le (q-1)-p+1\)，因此原结论仍然成立。如果\(i>k\)，那么由\(i\le r-p+1\)两边同时减去\(k\)和\(q-p+1\)后，得到\(i-k\le r-q\)，可以写成\(i-k\le r-(q+1)+1\)。故原结论成立。

由于\(1\le i\le r-p+1\)恒成立，因此\(r-p+1\ge 1\)，即\(p\le r\)恒成立，因此不会产生对空数组的调用。

9.2-2

1
2
3
4
5
6
7
8
9
10
11
ITERATIVE-RANDOMIZED-SELECT(A, p, r, i)
  while p < r
    q = RANDOMIZED-PARTITION(A, p, r)
    k = q – p + 1
    if i == k
      return A[q]
    elseif i < k
      r = q - 1
    else
      p = q + 1
      i = i - k

9.2-3

最坏的划分是从大到小选取了\(9,8,7,6,5,4,3,2,1,0\)时的划分情况。如下是划分的过程：

\(\begin{aligned} &[2, 3, 0, 5, 7, 9, 1, 8, 6, 4]\\ 9:&[2, 3, 0, 5, 7, 4, 1, 8, 6, \underline{9}]\\ 8:&[2, 3, 0, 5, 7, 4, 1, 6, \underline{8}, 9]\\ 7:&[2, 3, 0, 5, 6, 4, 1, \underline{7}, 8, 9]\\ 6:&[2, 3, 0, 5, 1, 4, \underline{6}, 7, 8, 9]\\ 5:&[2, 3, 0, 4, 1, \underline{5}, 6, 7, 8, 9]\\ 4:&[2, 3, 0, 1, \underline{4}, 5, 6, 7, 8, 9]\\ 3:&[2, 1, 0, \underline{3}, 4, 5, 6, 7, 8, 9]\\ 2:&[0, 1, \underline{2}, 3, 4, 5, 6, 7, 8, 9]\\ 1:&[0, \underline{1}, 2, 3, 4, 5, 6, 7, 8, 9]\\ 0:&[\underline{0}, 1, 2, 3, 4, 5, 6, 7, 8, 9] \end{aligned}\)

9.2-4

本题将使用归纳法来证明。令\(T(n,k)\)表示输入长度为\(n\)的置换并且求解第\(k\)小值的运行时间。

当\(n=1\)时，可以发现不需要进行比较，直接返回结果即可。\(1\)阶置换的个数为\(1\)，故期望的运行时间和序列的顺序是独立的，即\(T(1,1)=\Theta(1)\)。

当\(n>1\)时，假设对于所有\(1\le k'\le n' < n\)，原结论都成立，即输入\(n'\)阶上的排列的期望运行时间和排列的顺序无关，其值为\(E[T(n',k')]\)。

考虑\(1\le k\le n\)，那么对于一个特定的\(n\)阶置换\(p\)，询问第\(k\)小的数的运行时间为\(T_p(k)\)，那么可以写出\(T_p(k)\)的递推式：

\(\begin{aligned} T_p(k)&=\dfrac{1}{n}\left(\sum_{i=1}^{k-1}T_{p[i+1:n]}(k-i)+\Theta(1)+\sum_{i=k+1}^{n}T_{p[1:i-1]}(k)\right)\\ &=\dfrac{1}{n}\left(\sum_{i=1}^{k-1}T(n-i,k-i)+\Theta(1)+\sum_{i=k+1}^{n}T(i-1,k)\right) & \qquad(A) \end{aligned}\)

这个递推式的三项分别对应了划分的\(3\)种情况：划分值过小，划分值相等，划分值过大。

其中，步骤\((A)\)应用了上面的假设，因为序列\(p[i+1:n],p[1,i-1]\)的长度必定小于\(n\)。经过变换后，可以发现\(T_p(k)\)的运行时间已经和置换\(p\)没有关系，因此可以用\(T(n,k)=T_p(k)\)来表示一个任意顺序\(n\)阶置换的运行时间。

因此，算法RANDOMIZED-SELECT的期望运行时间和排列的顺序是独立的。