算法导论8.4 Exercises 答案

8.4-1

放入每个桶后，得到如下结果：

\(\begin{aligned} &0 && \langle\rangle\\ &1 && \langle.13,.16\rangle\\ &2 && \langle.20\rangle\\ &3 && \langle.39\rangle\\ &4 && \langle.42\rangle\\ &5 && \langle.53\rangle\\ &6 && \langle.64\rangle\\ &7 && \langle.71,.79\rangle\\ &8 && \langle.89\rangle\\ &9 && \langle\rangle\\ \end{aligned}\)

按顺序合并全部序列后，得到\(\langle.13,.16,.20,.39,.42,.53,.64,.71,.79,.89\rangle\)。

8.4-2

当每个元素都恰好分配到同一个桶中时，桶排序将会达到最坏的时间复杂度\(\Theta(n^2)\)，因为每个桶中内部的元素的排序方式是插入排序。

为了避免这种情况，可以考虑对桶内部的所有元素改用快速排序，堆排序等时间复杂度的上限为\(O(n\lg n)\)的算法。

8.4-3

\(X\)服从的是参数为\(n=2,p=\dfrac{1}{2}\)的二项分布，因此有\(E[X]=np=1,\text{Var}[X]=np(1-p)=0.5\)。

那么有\(E^2[X]=1^2=1,E[X^2]=E^2[X]+\text{Var}[X]=1+0.5=1.5\)。

8.4-4

假设针对这个序列使用的排序算法为BUCKET-SORT'，那么整个算法的过程如下：

BUCKET-SORT`(A, n)
  let B[0 : 9] be a new array
  for i = 0 to 9
    make B[i] an empty list
  for i = 1 to n
    k = ⌊A[i] * 10⌋
    // 此时每个桶B[k]中的元素都是[0, 1)均匀分布的。
    insert (A[i] - 0.1 * k) * n into list B[k]
  for i = 0 to 9
    BUCKET-SORT(B[i], B[i].size)
    for j = 1 to B[i].size
      B[i, j] = 0.1 * i + B[i, j] / n
  concatenate the lists B[0], B[1], ... , B[9] together in order
  return the concatenated lists

由于每个小桶\(B[i]\)的数都是来自\([0,1)\)均匀分布的，按照BUCKET-SORT算法的分析，这时每个小桶中运行BUCKET-SORT的期望时间复杂度为\(O(|B[i]|)\)。最终整个算法的时间复杂度为\(O(n)\)。

\(\star\) 8.4-5

在单位圆内随机选择一个点，令随机变量\(R\)表示这个点和原点的距离，那么有：\(\Pr\{R\le r\}=\dfrac{\pi r^2}{\pi \cdot 1^2}=r^2\)。

为了使划分的区域更加均匀，那么考虑所有\(n\)分为点，其中第\(i\)个分为点\(r_i\)的位置满足\(r_i^2=\dfrac{i}{n}\)，即\(r_i=\sqrt{\dfrac{i}{n}}\)。

那么，如果一个点\(A_j(x_j,y_j)\)满足\(r_{i-1}\le\sqrt{x_j^2+y_j^2}<r_i\)，那么\(A_j\)将会放进桶\(B[i]\)。接下来再将桶中的所有点进行插入排序即可。

由于每个点被分配进的桶的概率都是一样的，因此按照之前对桶排序的分析，这个算法仍然有\(\Theta(n)\)的平均时间复杂度。

\(\star\) 8.4-6

可以知道，\(n\)分位点的第\(i\)个分位点\(a_i\)满足\(P(a_i)=\dfrac{i}{n}\)。按照题目中的条件，\(a_i\)可以以\(O(1)\)的时间复杂度计算出来。第\(i\)个桶装的元素在区间\([a_{i-1},a_i)\)中。

那么对于每个具体的值\(X_i=x_i\)，它应该放在桶\(B[\lfloor n\cdot P(x_i)\rfloor]\)。由此，对于每个元素\(x_i\)，它被分配进每个桶的概率都是一样的。因此按照之前对桶排序的分析，这个算法仍然有\(\Theta(n)\)的平均时间复杂度。