算法导论11.2 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 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)\)。