算法导论8.4 Exercises 答案

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

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'，那么整个算法的过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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}}$。

那么，如果一个点$Aj(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$个分位点$ai$满足$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)$的平均时间复杂度。