算法导论5 Problems 答案

发表于 2022-12-20 更新于 2023-07-03 分类于算法导论阅读次数：本文字数： 2.5k 阅读时长 ≈ 2 分钟

5-1

a

假设第\(i\)执行INCREMENT操作提升的计数为\(X_i\)。那么最终\(n\)次操作完成后，提升的计数为\(X=X_1+X_2+\dots+X_n\)。

对于任何一个计数器值\(j\)，有\(\dfrac{1}{n_{j+1}-n_j}\)的概率提升\(n_{j+1}-n_j\)，有\(1-\dfrac{1}{n_{j+1}-n_j}\)的概率没有任何提升，因此有

\(\begin{aligned} E[X_i]&=0\cdot\Pr\{\text{unchange}\}+(n_{j+1}-n_j)\cdot\Pr\{\text{increase}\}\\ &=0\cdot\left(1-\dfrac{1}{n_{j+1}-n_j}\right) + (n_{j+1}-n_j)\cdot \dfrac{1}{n_{j+1}-n_j}\\ &=1 \end{aligned}\)

最终消去了\(j\)值。

因此\(\displaystyle{E[X]=E\left[\sum_{i=1}^nX_i\right] = \sum_{i=1}^nE[X_i]= n\cdot 1=n}\)。

b

\(\begin{aligned} E[X_i^2]&=0\cdot\Pr\{\text{unchange}\}+(n_{j+1}-n_j)^2\cdot\Pr\{\text{increase}\}\\ &=0\cdot\left(1-\dfrac{1}{n_{j+1}-n_j}\right) + (n_{j+1}-n_j)^2\cdot \dfrac{1}{n_{j+1}-n_j}\\ &=n_{j+1}-n_j\\ &=100(j+1)-100j\\ &=100\\ \\ \text{Var}[X_i]&=E[X^2_i]-E^2[X_i]\\ &=100-1\\ &=99 \end{aligned}\)

由于\(X_1,X_2,\dots,X_n\)是相互独立的，因此\(\displaystyle{\text{Var}[X]=\text{Var}\left[\sum_{i=1}^nX_i\right] = \sum_{i=1}^n\text{Var}[X_i]= n\cdot 99=99n}\)。

5-2

a

RANDOM-SEARCH(A, n, x)
  //假设FLAG是一个标志，它和A中的所有数都不相同。
  c = 0
  while c < n
    p = RANDOM(1, n)
      if A[p] == x
        return p
    if A[p] != FLAG
      A[p] = FLAG
      c = c + 1
  return "NOT FOUND"

b

可以发现，每一次while循环的执行过程相当于在参数为\(\dfrac{1}{n}\)的指数分布中进行抽样，因此需要抽样\(A\)的下标的期望次数为\(n\)。

c

可以发现，每一次while循环的执行过程相当于在参数为\(\dfrac{k}{n}\)的指数分布中进行抽样，因此需要抽样\(A\)的下标的期望次数为\(\dfrac{n}{k}\)。

d

假设随机变量\(X_i\)表示仍然剩下\(i\)个坐标仍然未被访问时，随机访问到这\(i\)个坐标的期望值。那么在整个RANDOM-SEARCH的调用过程中，访问下标的总次数为\(X=X_1+X_2+\dots+X_n\)。

可以发现，\(X_i\)服从参数为\(\dfrac{i}{n}\)的指数分布，因此\(E[X_i]=\dfrac{n}{i}\)。因此有\(\displaystyle{E[X]=E\left[\sum_{i=1}^nX_i\right]=\sum_{i=1}^nE[X_i]=\sum_{i=1}^n\dfrac{n}{i}=n\sum_{i=1}^n\dfrac{1}{i}=n(\ln n+O(1))}\)。

e

由于出现的排列都是等可能的，因此\(x\)在每个位置出现的概率都相同，因此平均查找时间为\(\displaystyle{\sum_{i=1}^n i\cdot \dfrac{1}{n}}=\dfrac{n+1}{2}\)。最坏查找时间明显为\(n\)。

f

最坏查找时间为\(n-k+1\)。

假设示性变量\(X_i\)表示下标元素\(A[i]\)中被访问过，那么总共访问的下标数为\(X=X_1+X_2+\dots+X_n\)。

对于\(A[i]\neq x\)的\(i\)，\(A[i]\)一定要放在\(k\)个\(x\)元素前面才能访问到，如果放在任何一个的后面，那么就会因为提前返回而无法访问，此时\(E[X_i]=\dfrac{1}{k+1}\)。

对于\(A[i']=x\)的\(i'\)，\(A[i']\)一定要放在这\(k\)个\(x\)中的第一个才能被访问到，如果放在任何一个的后面，那么就会因为提前返回而无法访问，此时\(E[X_{i'}]=\dfrac{1}{k}\)。

因此\(\displaystyle{E[X]=E\left[\sum_{i=1}^nX_i\right] = \sum_{i=1}^nE[X_i]= k\cdot \dfrac{1}{k} + (n-k)\cdot \dfrac{1}{k+1}=\dfrac{n+1}{k+1}}\)。

g

无论是平均还是最坏查找时间，都为\(n\)。

h

和算法DETERMINISTIC-SEARCH一样，如果\(k=0\)，那么无论平均还是最坏查找时间，都为\(n\)；如果\(k\ge 1\)，那么最坏查找时间为\(n-k+1\)，平均查找时间为\(\dfrac{n+1}{k+1}\)。

i

使用算法DETERMINISTIC-SEARCH最好。

对于算法DETERMINISTIC-SEARCH。在平均情况下，DETERMINISTIC-SEARCH的平均时间是算法RANDOM-SEARCH的一半。如果\(A\)不存在目标元素\(x\)，算法DETERMINISTIC-SEARCH能够更快地结束。
对于算法of SCRAMBLE-SEARCH。与其先对数组\(A\)进行乱序，还不如直接像DETERMINISTIC-SEARCH那样直接查找。由于平均查找时间和最坏查找时间都一样，这个算法先对\(A\)乱序显得多余。