算法导论16.4 Exercises 答案

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

16.4-1

在本次操作中，实际代价\(c_1=1\)，因为实际上只开放并处理了\(1\)个位置。

在第一个操作前，整个表都是空的，也没有位置存放，因此有\(num_0=size_0=0\)。

当存入第\(1\)个元素后，程序为其开辟了一个空间并将元素存入，因此有\(num_1=size_1=1\)。

根据方程16.4，可以给出\(\Phi_0=0,\Phi_1=1\)，故有\(\Delta \Phi_1=\Phi_1-\Phi_0=1\)。

因此第一次插入的均摊代价为\(\widehat{c_1}=c_1+\Delta\Phi_1=2\)。

16.4-2

因为定理和推论11.6-8说明，当装载因子\(\alpha\)无限趋近于\(1\)时，无论是单次插入一个元素还是查找一个元素，它们的探测次数期望都趋向于无穷大，此时无法用一个常数来限定查找次数的期望。为此，设计哈希表时，如果装载元素的个数比率到达某个小于\(1\)的上限值时，就将哈希表进行扩张。

1
2
3
4
5
6
7
8
9
10
11
12
13
TABLE-INSERT'(H, x)
  if H.size == 0
    allocate H.table with 1 slot
    H.size = 1
  // H.c是哈希表H装载因子的上限值，为一个常数。
  if H.num >= H.size * H.c
    allocate new-table with 2 ⋅ H.size slots
    insert all items in Table into new-table
    free H.table
    H.table = new-table
    H.size = 2 · H.size
  insert x into H.table
  H.num = H.num + 1

动态哈希表插入算法TABLE-INSERT'和动态变长数组插入算法TABLE-INSERT基本相同，均摊时间复杂度为\(O(1)\)。至于单次操作不一定是\(O(1)\)的原因是当第\(2\)个if满足时，算法将会为哈希表\(H\)开拓新的空间，并且将所有元素插入到新的哈希表中，此时单次操作的时间复杂度为线性。

16.4-3

当\(\alpha<\dfrac{1}{2}\)时，

  • 如果进行插入操作，直接支付\(1\)美元用于插入，不需要预支；

  • 如果进行删除操作，那么支付\(2\)美元，其中\(1\)美元用于支付当前元素的删除，另\(1\)美元进行预支，用于第\(size_i/2-num_i+1\)个元素在收缩转移时的预支。如果引起了收缩，那么由于每个元素在之前都进行了\(1\)美元的预支，因此将它们进行转移并不需要额外支付代价。

当\(\alpha\ge\dfrac{1}{2}\)时，

  • 如果进行插入操作，那么支付\(3\)美元，其中\(1\)美元用于直接插入。剩下\(2\)美元进行预支，其中\(1\)美元用于当前元素在扩张转移时的预支，另外\(1\)美元用于第\(num_i-size_i/2+1\)个元素在扩张转移时的预支。如果引起了扩张，那么由于每个元素在之前都进行了\(1\)美元的预支，因此将它们进行转移并不需要额外支付代价。

  • 如果进行删除操作，直接支付\(1\)美元用于删除，不需要预支；

由于所有操作中，每次支付的代价都不超过\(3\)美元，因每个操作均摊后的代价为\(O(1)\)。

16.4-4

分别进行\(3\)种情况的考虑，假设第\(i\)个操作为删除操作。

  • 当\(\alpha>\dfrac{1}{2}\)时，\(\Phi_{i-1}=2num_{i-1}-size_{i-1},\Phi_i=2(num_{i-1}-1)-size_i\)。

由于没有发生收缩操作，因此\(size_i=size_{i-1},c_i=1\)。最终有

\(\begin{aligned} \widehat{c_i}&=c_i+\Phi_i-\Phi_{i-1}\\ &=1+(2(num_{i-1}-1)-size_i)-(2num_{i-1}-size_{i-1})\\ &=-1 \end{aligned}\)

  • 当\(\dfrac{1}{3}<\alpha\le \dfrac{1}{2}\)时，\(\Phi_{i-1}=size_{i-1}-2num_{i-1},\Phi_i=size_i-2(num_{i-1}-1)\)。

由于没有发生收缩操作，因此\(size_i=size_{i-1},c_i=1\)。最终有

\(\begin{aligned} \widehat{c_i}&=c_i+\Phi_i-\Phi_{i-1}\\ &=1+(size_i-2(num_{i-1}-1))-(size_{i-1}-2num_{i-1})\\ &=3 \end{aligned}\)

  • 当\(\dfrac{1}{3}<\alpha\le \dfrac{1}{2}\)时，\(\Phi_{i-1}=size_{i-1}-2num_{i-1},\Phi_i=size_i-2(num_{i-1}-1)\)。

由于发生了收缩操作，因此\(size_i=\dfrac{2}{3}\cdot size_{i-1}\)。这个过程复制了\(\dfrac{1}{3}\cdot size_{i-1}\)个元素，因此\(c_i=\dfrac{1}{3}\cdot size_{i-1}\)。最终有

\(\begin{aligned} \widehat{c_i}&=c_i+\Phi_i-\Phi_{i-1}\\ &=c_i+(size_i-2(num_{i-1}-1))-(size_{i-1}-2num_{i-1})\\ &=c_i+size_i-size_{i-1}\\ &=\dfrac{1}{3}\cdot size_{i-1}+\dfrac{2}{3}\cdot size_{i-1}-size_{i-1}+2\\ &=2 \end{aligned}\)

最终，无论哪种操作，它们的均摊代价最多不超过\(3\)，因此操作TABLE-DELETE的均摊代价有着常数上限。