算法导论11.2 Exercises 答案

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

11.2-1

考虑使用示性随机变量$X_{i,j}$表示$k_i$和$k_j$发生了哈希碰撞。那么有

$\displaystyle{E[X{i,j}]=\sum{x=0}^{m-1}\Pr{h(k_i)=x\land h(k_j)=x}=m\cdot \dfrac{1}{m^2}=\dfrac{1}{m}}$

假设随机变量$Y$表示产生的碰撞数，也就是题目中所求值，即有$\displaystyle{Y=\sum{i=1}^{n-1}\sum{j=i+1}^nX_{i,j}}$，那么有

$\displaystyle{E[Y]=E\left[\sum{i=1}^{n-1}\sum{j=i+1}^nX{i,j}\right]=\sum{i=1}^{n-1}\sum{j=i+1}^nE[X{i,j}]=\dfrac{n(n-1)}{2}\cdot\dfrac{1}{m}=\dfrac{n(n-1)}{2m}}$

11.2-2

最终将会变成如下形式，因为后来的元素先插入链表头部。

$\begin{array}{|l|l|} \hline
h(k) &\text{keys}\
\hline
0&\
\hline
1&10,19,28\
\hline
2&20\
\hline
3&12\
\hline
4&\
\hline
5&5\
\hline
6&33,15\
\hline
7&\
\hline
8&17\
\hline
\end{array}$

11.2-3

成功查找：基本没有影响，仍然是$O(1+\alpha)$。

不成功查找：如果查找的第一个key超过了所要查找的key，那么可以立刻返回查找失败。虽然快了一些，不过时间复杂度仍然是$O(1+\alpha)$。

插入：插入操作是先找到小于当前key的最大值节点后面再进行插入。因此时间复杂度和成功查找时基本一致，为$O(1+\alpha)$。

删除：如果维护的链表是双向链表，那么删除操作的时间复杂度为$O(1)$；如果是单项链表，那么还需要查找到这个节点的前驱节点，与成功查找操作一样，为$O(1+\alpha)$。

11.2-4

这个哈希表内部的自由链表使用了一个双向链表来实现。这个哈希表中，它们都有一个占用标志变量，表示这个槽位是否被占用。如果槽位被占用，那么就有一个元素指向对应的链表。此外，槽位还有两个方向的指针用来维护这个自由链表。

  • INSERT: 在对应的链表T[x.key]上直接以$O(1)$的时间插入元素。如果槽位T[x.key]标志变量为$0$，那么将其置$1$，新建一个自由节点并插入这个自由链表中，然后让这个自由节点的元素指向一个初始化的空链表，再将这个元素插入到这个链表中。

  • DELETE: 在对应的链表T[x.key]上删除元素。如果删除完后，这个链表为空，那么槽位T[x.key]的标志变量置为$0$，并且将自由节点从这个自由链表上删去。由于自由链表是双向链表，因此删除操作可以达到$O(1)$。

  • SEARCH: 直接将对应链表的表头元素返回即可。如果没有，那么直接返回NIL。整个操作仅需要$O(1)$的时间。

如果使用的是单向链表，那么删除操作并不能达到$O(1)$，而是$O(1+\alpha)$。因此只能使用双向链表。

11.2-5

当这$|U|$个不同的键均匀地分配到每个槽中时，包含了最多键的那个槽的大小$\displaystyle{t=\max_{i=0}^{m-1}{|T(i)|}}$才能最小化。那么有$t\ge \left\lceil\dfrac{|U|}{m}\right\rceil>\dfrac{(n-1)m}{m}=n-1$。这说明，包含最多键的那个槽至少会包含$n$个键。由这个槽里的所有键可以构造出一个大小为$n$的集合$S$，里面的所有键将会哈希到这一个槽中。

11.2-6

随机选择操作由算法RANDOM-HASH-TABLE-SELECT(T)给出。

1
2
3
4
5
6
RANDOM-HASH-TABLE-SELECT(T)
  while True
    k = RANDOM(0, T.m - 1)
    p = RANDOM(1, K)
    if 1 <= p and p <= T[k].size
      return the p-th element of list T[k]

在一次随机选择中，每个元素被中的概率为$\dfrac{1}{mL}$。由于哈希表$T$中有$n$个元素，因此在一次随机选择中有$\dfrac{n}{mL}=\dfrac{\alpha}{L}$概率选中哈希表的元素并返回。

令随机变量$X$表示这个算法的while循环迭代次数。那么按照上面的结论，$X$服从参数为$\dfrac{\alpha}{L}$的几何分布。因此，$X$的期望值为$\dfrac{L}{\alpha}$。

找到了一个元素的下标后，还需要遍历链表才能够真正找到这个元素。由于链表的最大长度为$L$，因此遍历的时间最多为$L$。

最终，算法的平均时间复杂度为$O\left(L+\dfrac{L}{\alpha}\right)=O\left(L\cdot\left(1+\dfrac{1}{\alpha}\right)\right)$。