算法导论27.2 Exercises 答案

发表于 2023-07-25 分类于算法导论阅读次数：本文字数： 3.1k 阅读时长 ≈ 3 分钟

27.2-1

由于每次查询都是相互独立的，因此假设每一次查询需要进行检索的期望值为$e$（与查询的序号无关）。由于需要检索关键字的概率为$x_i$，因此这时$e$值为

$\begin{aligned} e&=\sum_{k=1}^n k\cdot\left(\sum_{x\in S\land r_L(x)=k} p(x)\right)\\ &=\sum_{i=1}^n r_L(x_i)\cdot p(x_i) \end{aligned}$

因此$m$次查询的总期望次数为$\displaystyle{me=m\sum_{i=1}^n r_L(x_i)\cdot p(x_i)}$。

如果$L$中的关键字$x_i$不是按照查询概率$p$从大到小出现的，那么必定存在一对不同的关键字$x_j,x_k$，使得$r_L(x_j)<r_L(x_k)$并且有$p(x_j)<p(x_k)$。那么考虑新构造的静态表$L'$，它是将关键字$x_j$和$x_k$进行了交换，由此可见$r_L(x_i)=r_{L'}(x_j),r_L(x_j)=r_{L'}(x_i)$。考虑计算静态表上$L'$进行一次检索的花费的期望值，可以得到$\displaystyle{e'=\sum_{i=1}^n r_{L'}(x_i)\cdot p(x_i)}$。

那么得到

$\begin{aligned} e'-e&=p(x_j)\cdot r_{L'}(x_j)+p(x_k)\cdot r_{L'}(x_k)-p(x_j)\cdot r_{L}(x_j)-p(x_k)\cdot r_{L'}(x_k)\\ &=p(x_j)(r_{L'}(x_j)-r_{L}(x_j))+p(x_k)(r_{L'}(x_k)-r_{L}(x_k))\\ &=p(x_j)(r_{L}(x_k)-r_{L}(x_j))+p(x_k)(r_{L}(x_j)-r_{L}(x_k))\\ &=p(x_j)(r_{L}(x_k)-r_{L}(x_j))-p(x_k)(r_{L}(x_k)-r_{L}(x_j))\\ &=(p(x_j)-p(x_k))(r_{L}(x_k)-r_{L}(x_j))\\ &<0 \end{aligned}$

因此$L$不是使查找期望数最小的静态表。最终，只有按照$p(x_i)$降序的静态表才是所求的。

27.2-2

这个结论是错误的。FORESEE考虑的是全局最优的策略，每一个步骤的开销都并非比MOVE-TO-FRONT优秀。

考虑对序列$\langle 1,2,3,4,5\rangle$，接下来$3$次搜索分别是检索$3,5,5$，那么有

$\begin{array}{c|ccccc|ccccc} \begin{array}{c}\text{element}\\\text{searched}\end{array} &L&\begin{array}{c}\text{search}\\\text{cost}\end{array}&\begin{array}{c}\text{swap}\\\text{cost}\end{array}&\begin{array}{c}\text{search +}\\\text{swap}\\\text{cost}\end{array}&\begin{array}{c}\text{cumulative}\\\text{cost}\end{array}&L&\begin{array}{c}\text{search}\\\text{cost}\end{array}&\begin{array}{c}\text{swap}\\\text{cost}\end{array}&\begin{array}{c}\text{search +}\\\text{swap}\\\text{cost}\end{array}&\begin{array}{c}\text{cumulative}\\\text{cost}\end{array}\\\hline 3&\langle 1,2,3,4,5\rangle&3&4&7&7&\langle 1,2,3,4,5\rangle&3&2&5&5\\ 5&\langle 5,1,2,3,4\rangle&1&0&0&8&\langle 3,1,2,4,5\rangle&5&4&9&14\\ 5&\langle 5,1,2,3,4\rangle&1&0&0&9&\langle 5,3,1,2,4\rangle&1&0&0&15 \end{array}$

可见在这个检索序列中，FORESEE的总操作开销小于MOVE-TO-FRONT的总操作，但是FORESEE的第一步开销大于MOVE-TO-FRONT的第一步开销，从而证伪原结论。

27.2-3

结论：这种通过关键字的访问次数维护表$L$的策略并非是常数竞争比例的。

考虑一个表$L$中有如下关键字：$\langle 1,2,3,\dots,n\rangle$，以及一个访问序列：首先进行$n$次对$1$的访问，然后进行$n$次对$2$的访问，接下来进行$n$次对$3$的访问……最后对$n$进行$n$次访问。也就是说，一共对表$L$进行了$n^2$次检索。在这个过程中，不失一般性，如果存在元素的访问次数相同，那么对列表重排后，相同访问次数的元素相对顺序不变。那么在这个过程中，表$L$所有的关键字的顺序将会维持不变（因为访问次数全程都是非递增的）。

在这$n^2$检索中，对于第$(k-1)n+1$到第$kn$次访问（其中$k\in[1,n]$），都是访问$L$中的第$k$个元素，所花费的代价为$k$。因此，这$n^2$次操作的代价为$\displaystyle{c_1(n)=\sum_{k=1}^nnk=n\cdot \dfrac{n(n+1)}{2}=\dfrac{n^2(n+1)}{2}}$。

考虑使用MOVE-TO-FRONT算法充当FORESEE算法的角色。对于第$(k-1)n+1$到第$kn$次访问中，第$k(n-1)$次访问使用了$k$的开销寻找到了这个元素，并且用$k-1$的开销将其移动到最前面，因此总共有$2k-1$的开销；而第$(k-1)n+2$到第$kn$次访问中，仅仅使用了$1$的代价用于寻找。因此，这$n^2$次操作的代价为$\displaystyle{c_2(n)=\sum_{k=1}^n(2k-1+n-1)=n^2-2n+n(n+1)=2n^2-n}$。

可见，$\dfrac{c_1(n)}{c_2(n)}=O(n)$，因此这种策略不是常数竞争比例的。

27.2-4

如果MOVE-TO-FRONT算法移动元素不需要花费任何的代价，那么方程27.3可以改写成：

$c_i^M=r_