算法导论 7.2 Exercises 答案

7.2-1

假设 $T(n)\le c{n}^2-d$，那么有

针对 $f(n)=\mathrm{\Theta }(n)$，可以知道 $\mathrm{\exists }{c}_0,n_0>0,\mathrm{\forall }n\ge n_0,0\le n\le c_{0}n$ 成立。因此假设 $n\ge n_0$，那么有

$\begin{array}{rl}T(n)& =T(n-1)+\mathrm{\Theta }(n)\\ & \le c(n-1{)}^2-d+c_{0}n\\ & \le c{n}^2-2cn+c-d+c_{0}n\\ & =c{n}^2-(d-c)-(2cn-c_{0}n)\\ & \le c{n}^2-(2cn-c_{0}n)& (A)\\ & \le c{n}^2& (B)\end{array}$

其中，步骤 $(A)$ 假设了 $d\ge c$ 成立。步骤 $(B)$ 假设了 $2c\ge c_0$。最终，由数学归纳法，原结论 $T(n)=O(n^2)$ 成立。

假设 $T(n)\ge c^{\prime }{n}^2$，那么有

$\begin{array}{rl}T(n)& =T(n-1)+\mathrm{\Theta }(n)\\ & \ge c^{\prime }(n-1{)}^2+\mathrm{\Theta }(n)\\ & =c^{\prime }{n}^2-2c^{\prime }n+c^{\prime }+\mathrm{\Theta }(n)\\ & \ge c^{\prime }{n}^2-2c^{\prime }n+\mathrm{\Theta }(n)\\ & =c^{\prime }{n}^2-(2c^{\prime }n-\mathrm{\Theta }(n))\\ & \ge c^{\prime }{n}^2& (A)\end{array}$

其中步骤 $(A)$ 假设了 $2c^{\prime }n$ 渐进上界比 $\mathrm{\Theta }(n)$ 大。

令 $c^{\prime }=min(1,T(1)),n_0=1$。由于 $T(1)\ge c^{\prime }\ge c^{\prime }{n}^2$，那么由数学归纳法，结论 $T(n)=\mathrm{\Omega }(n^2)$ 成立。

因此，最终得到 $T(n)=\mathrm{\Theta }(n^2)$。

7.2-2

$\mathrm{\Theta }(n^2)$，因为每一次的划分都会将所有元素划分到同一侧。每进行一层递归只划分出了一个空数组和一个长度为 $n-1$ 的数组。因此根据题目 7.2-1 的结论，时间复杂度为 $\mathrm{\Theta }(n^2)$。

7.2-3

由于序列已经排好序，因此算法 PARTITION 每次选择的支点都将会是最小值。最终算法 PARTITION 完成后，支点到达了最左端，并且所有元素都在右侧，依然保持降序。和题目 7.2-2 一样，每进行一层递归只划分出了一个空数组和一个长度为 $n-1$ 的数组。因此根据题目 7.2-1 的结论，时间复杂度为 $\mathrm{\Theta }(n^2)$。

7.2-4

以下是插入排序算法的代码：

INSERTION-SORT(A, n)
  for i = 2 to n
    key = A[i]
    j = i – 1
    while j > 0 and A[j] > key
      A[j + 1] = A[j]
      j = j – 1
    A[j + 1] = key

考虑使用逆序数 $I$ 来衡量一个序列的排序程度。如果逆序数越小，可以认为排序程度越小。

根据题目 2-4-c 的结论，插入排序的时间复杂度为 $O(n+I)$。如果逆序数越小，说明插入排序的效率越高。

如果一个序列 $A$ 排序程度越高，那么在使用算法 PARTITION 进行划分时，在 $A[p:r]$ 取到的支点 $A[r]$ 可能在 $A[p:r]$ 中是比较接近最大值的。那么最终划分完成后，左侧元素数量比右侧多很多，从而划分情况不是特别理想。此时糟糕的划分将会导致快速排序算法效率不会太好。

因此，总而言之，对一个接近排序的数组进行排序使用插入排序效果比快速排序好。

7.2-5

不失一般性，假设分得的 $\alpha$ 一直在左侧，否则可以旋转整个区间。

那么，递归树的左侧深度是满足最小的 $h$，使得 $n\cdot {\alpha }^h\le 1$ 成立，从而得到 $h\ge {\log }_{\alpha }1/n$。经过对数的变换，最终得到 $h\ge {\log }_{1/\alpha }n$。因此最浅的叶子节点高度为 $h\ge {\log }_{1/\alpha }n$。同理，可以计算出最深叶子节点高度为 ${\log }_{1/\beta }n$。

7.2-6

由于所有排列出现的概率都均等，因此出现在数组 $A$ 最后一个数的概率是均等的。对于一个长度为 $n$ 的数组，如果最后一个数是第 $i$ 小的，那么使用算法 PARTITION 进行划分后，将会有 $i$ 个元素在左侧（包括支点），$n-i$ 个元素在右侧，划分比例为 ${\displaystyle \frac{i}{n}}:{\displaystyle \frac{n-i}{n}}$。可以发现，当 $j=n+1-i$ 时，划分比例是一样的。

因此，不失一般性，仅仅考虑 $i\le n/2$ 时的情况。划分的元素是第 $i$ 小时，只有当 $j$ 满足 $i<j<n+1-i$ 时，以 $j$ 划分才会更均匀，这样的 $j$ 一共有 $n+1-i-i-1=n-2i$ 个，占比 ${\displaystyle \frac{n-2i}{n}}=1-{\displaystyle \frac{2i}{n}}$。

因此令 $\alpha =i/n$。对于任意常数 $\alpha$ 产生比 $1-\alpha :\alpha$ 更好的划分的概率为 $1-2\alpha$。