算法导论11.4 Exercises 答案

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

11.4-1

线性探测的过程如下：

\(\begin{array}{c} 0:\\1:\\2:\\3:\\4:\\5:\\6:\\7:\\8:\\9:\\10:\\ \end{array} \begin{array}{|c|} \hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline31\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline\\\hline4\\\hline\\\hline\\\hline\\\hline\\\hline31\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline\\\hline4\\\hline15\\\hline\\\hline\\\hline\\\hline31\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline\\\hline4\\\hline15\\\hline28\\\hline\\\hline\\\hline31\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline\\\hline4\\\hline15\\\hline28\\\hline17\\\hline\\\hline31\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline88\\\hline\\\hline\\\hline4\\\hline15\\\hline28\\\hline17\\\hline\\\hline31\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline88\\\hline\\\hline\\\hline4\\\hline15\\\hline28\\\hline17\\\hline59\\\hline31\\\hline 10\\\hline \end{array}\)

二次探测的过程如下：

\(\begin{array}{c} 0:\\1:\\2:\\3:\\4:\\5:\\6:\\7:\\8:\\9:\\10:\\ \end{array} \begin{array}{|c|} \hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline31\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline\\\hline4\\\hline\\\hline\\\hline\\\hline\\\hline31\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline\\\hline4\\\hline\\\hline\\\hline\\\hline15\\\hline31\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline\\\hline4\\\hline\\\hline28\\\hline\\\hline15\\\hline31\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline17\\\hline4\\\hline\\\hline28\\\hline\\\hline15\\\hline31\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline88\\\hline17\\\hline4\\\hline\\\hline28\\\hline\\\hline15\\\hline31\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline88\\\hline17\\\hline4\\\hline\\\hline28\\\hline59\\\hline15\\\hline31\\\hline 10\\\hline \end{array}\)

双重散列的过程如下：

\(\begin{array}{c} 0:\\1:\\2:\\3:\\4:\\5:\\6:\\7:\\8:\\9:\\10:\\ \end{array} \begin{array}{|c|} \hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline\\\hline31\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline\\\hline4\\\hline\\\hline\\\hline\\\hline\\\hline31\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline\\\hline4\\\hline15\\\hline\\\hline\\\hline\\\hline31\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline\\\hline4\\\hline15\\\hline28\\\hline\\\hline\\\hline31\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline17\\\hline4\\\hline15\\\hline28\\\hline\\\hline\\\hline31\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline\\\hline17\\\hline4\\\hline15\\\hline28\\\hline88\\\hline\\\hline31\\\hline 10\\\hline \end{array} \rightarrow \begin{array}{|c|} \hline22\\\hline\\\hline59\\\hline17\\\hline4\\\hline15\\\hline28\\\hline88\\\hline\\\hline31\\\hline 10\\\hline \end{array}\)

11.4-2

为了支持删除操作，需要对HASH-SEARCH, HASH-INSERT进行修改。另外删除操作由算法HASH-DELETE'给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
HASH-INSERT'(T, k)
  i = 0
  repeat
    q = h(k, i)
    if T[q] == NIL or T[q] == DELETED
      T[q] = k
      return q
    else i = i + 1
  until i == m
  error “hash table overflow”

// 也就是说，查找并不需要进行任何修改。
HASH-SEARCH'(T, k)
  return HASH-SEARCH(T, k)

HASH-DELETE'(T, k)
  q = HASH-INSERT'(T, k)
  T[q] = DELETED

11.4-3

\(\begin{array}{|c|c|c|} \hline \alpha & \texttt{unsuccessful}(E[\alpha]\le \dfrac{1}{1-\alpha}) & \texttt{successful}(E[\alpha]\le \dfrac{1}{\alpha} \ln \dfrac{1}{1-\alpha})\\ \hline \dfrac{3}{4} & 4 & \dfrac{4 \ln 4}{3} \approx 1.84839\\ \hline \dfrac{7}{8} & 8 & \dfrac{8 \ln 8}{7} \approx 2.73650\\ \hline \end{array}\)

11.4-4

令随机变量\(X_i\)表示第\(i\)个键插入所期望的时间，令随机变量\(S\)表示查找一次所期望的时间，假设每个键被查询的概率是相同的，并且插入的键各不相同，那么有\(\displaystyle{E[S]=E\left[\dfrac{1}{m}\sum_{n=1}^m X_n\right]=\dfrac{1}{m}\sum_{n=1}^m E[X_n]}\)。并且可以知道，一次查询键\(k\)的时间和当初插入键\(k\)的时间相等，而当初插入键\(k\)的时间就相当于插入\(k\)前一次不成功查找的时间。因此，令随机变量\(Y_n\)表示当填充因子为\(\dfrac{n}{m}(0\le n< m)\)时，进行一次不成功查找的时间。可以知道\(Y_{n}=X_{n+1}\)。根据定理11.6的结果，有\(E[Y_n]\le \dfrac{1}{1-n/m}=\dfrac{m}{m-n}\)。

最终计算\(E[S]\)的值，有

\(\begin{aligned} E[S]&=\dfrac{1}{m}\sum_{n=1}^m E[X_n]\\ &=\dfrac{1}{m}\sum_{n=0}^{m-1} E[Y_n]\\ &\le \dfrac{1}{m}\sum_{n=0}^{m-1}\dfrac{m}{m-n}\\ &= \sum_{n=0}^{m-1}\dfrac{1}{m-n}\\ &= \sum_{n=1}^{m}\dfrac{1}{n}\\ &= H_m \end{aligned}\)

\(\star\) 11.4-5

令集合\(S=\{h(k,i)|i\in \mathbb{Z}_m\}\)。那么在一次不成功的查找中，它需要探测\(t=|S|\)个槽。因此，此时我们考虑集合\(S\)的大小\(t\)。根据同余的性质，可知\(t=|(\{h_1(k)+i\cdot h_2(k))\bmod m|i\in \mathbb{Z}_m\}|=|\{i\cdot h_2(k)\bmod m|i\in \mathbb{Z}_m\}|\)。令\(S'=\{i\cdot h_2(k)\bmod m|i\in \mathbb{Z}_m\}\)。

如果一个数\(v\in S'\)，当且仅当关于\(i\)的同余方程\(i\cdot h_2(i)\equiv v\pmod m\)有解，根据推论31.21，有\(d\mid v\)。因此，\(t=\dfrac{m}{d}\)。

也就是说，在这一次不成功的查找中，将会有\(\dfrac{1}{d}\)的槽会被探测。当\(d=1\)时，所有的槽都将会被探测。

\(\star\) 11.4-6

令\(\alpha\)为装填因子。进行一次不成功查找的期望探测次数的上界为\(\dfrac{1}{1-\alpha}\)，进行一次成功查找的期望探测次数的上界为\(\dfrac{1}{\alpha} \ln \dfrac{1}{1-\alpha}\)。如果不成功查找的期望探测次数为成功时的两倍，通过上界估计，可以列出方程：

\[\dfrac{1}{1-\alpha}=2\cdot \dfrac{1}{\alpha} \ln \dfrac{1}{1-\alpha}\]

这个方程无法手动求解。考虑使用Mathematica代码NSolve[1/(1 - x) == 2/x*Log[1/(1 - x)], x]进行计算，最终得到结果\(\alpha \approx 0.715332\)。