Problem 1 (教材习题 5-1)

（概率计数） 利用一个 $b$ 位的计数器，我们一般只能计数到 $2^b - 1$ 。而用 R.Morris 的 概率计数法 ，我们可以计数到一个大得多的值，代价是精度有所损失。

对 $i = 0, 1, \cdots, 2^b - 1$ ，令计数器值 $i$ 表示 $n_i$ 的计数，其中 $n_i$ 构成了一个非负的递增序列。假设计数器初值为 $0$ ，表示计数 $n_0 = 0$ 。 INCREMENT 运算单元工作在一个计数器上，它以概率的方式包含值 $i$ 。如果 $i = 2^b - 1$ ，则该运算单元报告溢出错误；否则， INCREMENT 运算单元以概率 $1 / (n_{i+1} - n_i)$ 把计数器增加 $1$ ，以概率 $1 - 1/(n_{i+1} - n_i)$ 保持计数器不变。

对所有的 $i \ge 0$ ，若选择 $n_i = i$ ，此计数器就是一个普通的计数器。若选择 $n_i = 2^{i - 1} (i > 0)$ ，或者 $n_i = F_i$ （第 $i$ 个佩波那契数，参见作业3问题2），则会出现更多有趣的情形。

对于这个问题，假设 $n_{2^b - 1}$ 已经足够大，发生一个溢出错误的概率可以忽略。

1. 请说明在执行 $n$ 次 INCREMENT 操作后，计数器所表示的数期望值正好是 $n$ 。

2. 分析计数器表示的计数的方差依赖于 $n_i$ 序列。我们来看一个简单情形：对所有 $i \ge 0$ ， $n_i = 100i$ 。在执行了 $n$ 次 INCREMENT 操作后，请估计计数器所表示数的方差。

Solution

1. 我们只需要证明在执行 $1$ 次 INCREMENT 操作后，计数器所表示的数期望值正好是 $1$ 即可。

   • 假设当前计数器的值为 $i$ ，则其代表的数值为 $n_i$ ，将其代表的数值 $j$ 从 $n_i$ 增加到 $n_{i+1}$ 时，每次都会有 $1 / (n_{i+1} - n_{i})$ 的概率使得计数器的值加1，记增值为 $X_{n_i}$ ，则 $E[X_{n_i}] = 1 / (n_{i+1} - n_{i})$ 。

   • 记这次 INCREMENT 操作总的增值为 $X$ ，则 $X = \sum_{j = n_i}^{n_{i+1}} X_j$ 。于是

$E[X] = E[\sum_{j=n_i}^{n_{i+1}}X_j] = \sum_{j=n_i}^{n_{i+1}}E[X_j] = \sum_{j=n_i}^{n_{i+1}}\frac{1}{n_{i+1} - n_i} = \frac{n_{i+1} - n_i}{n_{i+1} - n_i} = 1$

2. 当 $n_i = 100 i$ 时，$n_{i+1} - n_{i} = 100$ 为定值，于是，每次 INCREMENT 会有 100 次其代表数值的变化，每次概率为 $p = 1/100$ 。在执行了 $n$ 次 INCREMENT 之后，记增值为 $Y$ ，$Y$ 的大小就是 $100n$ 次代表数值的变化中使得计数器值增加 1 的次数。

   • 于是 $Y \sim B(100n, p=0.01)$ ，是一个二项分布，从而 $D[Y] = 100np(1-p) = 0.99n$ 。

Problem 2 (教材习题 5-2)

（查找一个无序数组） 本题将分析三个算法，他们在一个包含 $n$ 个元素的无序数组 $A$ 中查找一个值 $x$ 。

考虑如下的随机策略：随机挑选 $A$ 中的一个下标 $i$ 。如果 $A[i] = x$ ，则终止；否则，继续挑选 $A$ 中一个新的随机下标。重复随机挑选下标，直到找到一个下标 $j$ ，使 $A[j] = x$ 或者直到我们已经检查过 $A$ 中的每一个元素。注意，我们每次都是从全部下标的集合中挑选，于是可能会不止一次地检查某个元素。

1. 请写出过程 RANDOM-SEARCH 的伪代码来实现上述策略。确保当 $A$ 中所有下标都挑选过时，你的算法应停止。

2. 假定恰好有一个下标 $i$ 使得 $A[i] = x$ 。在我们找到 $x$ 和 RANDOM-SEARCH 结束之前，必须挑选 $A$ 下标的数目期望是多少？

3. 假设有 $k \ge 1$ 个下标 $i$ 使得 $A[i] = x$ ，推广你对第2问的解答。在找到 $x$ 或 RANDOM-SEARCH 结束之前，必须挑选 $A$ 下标的数目期望是多少？你的答案应该是 $n$ 和 $k$ 的函数。

4. 假设没有下标 $i$ 使得 $A[i] = x$ 。在检查完 $A$ 的所有元素或 RANDOM-SEARCH 结束之前，我们必须挑选的 $A$ 的下标的数目期望是多少？

现在考虑一个确定性的线性查找算法，我们称之为 DETERMINSTIC-SEARCH 。具体地说，这个算法在 $A$ 中顺序查找 $x$ ，考虑 $A[1], A[2], A[3], \cdots, A[n]$ ，直到找到 $A[i] = x$ ，或者到达数组的末尾。假设输入数组的所有排列都是等可能的。

5. 假设恰好有一个下标 $i$ 使得 $A[i] = x$ 。 DETERMINSTIC-SEARCH 平均情形的运行时间是多少？ DETERMINSTIC-SEARCH 最坏情况的运行时间又是多少？

6. 假设有 $k \ge 1$ 个下标 $i$ 使得 $A[i] = x$ ，推广你对第5问的解答。 DETERMINSTIC-SEARCH 平均情形的运行时间是多少？ DETERMINSTIC-SEARCH 最坏情形的运行时间又是多少？你的答案应该是 $n$ 与 $k$ 的函数。

7. 假设没有下标 $i$ 使得 $A[i] = x$ 。 DETERMINSTIC-SEARCH 平均情形的运行时间是多少？ DETERMINSTIC-SEARCH 最坏情形的运行时间又是多少？

最后，考虑一个随机算法 SCRAMBLE-SEARCH ，它先将输入数组随机变换排列，然后在排列变换后的数组上，运行上面的确定性线性查找算法。

8. 设 $k$ 是满足 $A[i] = x$ 的下标的数目，请给出在 $k = 0$ 和 $k = 1$ 情况下，算法 SCRAMBLE-SEARCH 最坏情况的运行时间和运行时间期望。推广你的解答以处理 $k \ge 1$ 的情况。

9. 你将会使用 3 种查找算法中的哪一个？解释你的答案。

Solution

1. 算法伪代码如下：

其中，数组 $P$ 用于标记每个下标是否都已经被判断过。

2. 假设需要挑选 $X$ 次才能挑选到使得 $A[i] = x$ 的 $i$ ，每次都有 $1/n$ 的概率可以选到，于是 $X \sim g(1/n)$ ，由几何分布的期望公式有 $E[X] = n$ 。

3. 假设需要挑选 $X$ 次才能挑选到使得 $A[i] = x$ 的 $i$ ，每次都有 $k/n$ 的概率可以选到，于是 $X \sim g(k/n)$ ，由几何分布的期望公式有 $E[X] = n/k$ 。

4. 相当于球与箱子的问题。往 $b$ 个箱子里面连续随机扔球，在期望每个箱子都有球之前，大约需要投 $b \ln b$ 次，具体见第4讲PPT第24-25页。所以我们必须挑选的下标的数目期望为 $n\ln n$ 。

5. 考虑需要检查的元素个数来作为运行时间的考量标准。

记需要检查的元素个数为 $X$ ，则 $X = i$ 相当于 $A[i] = x$ ，而 $A$ 是随机排列的且其中只有 $1$ 个 $x$ ，于是 $Pr{X = i} = 1 / n$ ，其中 $i = 1, 2, …, n$ 。根据期望定义，有

$E[X] = \sum_{i=1}^{n} i \cdot Pr{X = i} = \sum_{i=1}^{n}\frac{i}{n} = \frac{n+1}{2}$

最坏情况为 $A[n] = x$ 的时候，需要检查全部 $n$ 个元素。

6. 依旧考虑需要检查的元素个数来作为运行时间的考量标准。

记第 $i$ 个元素被检查为事件 $H_i$ ， $X_i = I{H_i}$ ，则 $E[X_i] = Pr{H_i}$。

• 当 $A[i] \ne x$ 时， 第 $i$ 个元素被检查说明所有的 $A[a_j] = x(j = 1, 2, …, k)$ 都满足 $a_j > i$ ，否则 $i$ 就会被检查了；也就是说在 $a_1, a_2, …, a_k, i$ 这 $k + 1$ 个元素组成的排列中 $i$ 得排在第一个（其他元素无所谓），因此 $Pr{H_i} = 1 / (k+1)$ 。

• 当 $A[i] = x$ 时，第 $i$ 个元素被检查说明在这 $k$ 个值为 $x$ 的数组成的排列中， $i$ 得是第一个，因此 $Pr{H_i} = 1/ k$ 。

• 记所有等于 $x$ 的元素组成的集合为 $S$ ， $|S| = k$ ，所有被检查的元素个数为 $X$ ， $X = \sum_{i=1}^{n} X_i$ ，所以

$E[X] = E[\sum_{i=1}^{n} X_i] = \sum_{i=1}^{n} E[X_i] = \sum_{i=1}^{n} Pr{H_i}\$
=\sum_{i\notin S} Pr{H_i} + \sum_{i\in S} Pr{H_i}\
= \frac{n - k}{k+1} + \frac{k}{k} = \frac{n+1}{k+1}

因此，DETERMINSTIC-SEARCH 平均情况下需要检查 $(n + 1) / (k + 1)$ 个元素。

最坏情况是显然的，就是 $k$ 个 $x$ 恰好是最后 $k$ 个元素，需要检查 $n - k + 1$ 个元素。

7. 需要检查所有元素才能确认不存在 $A[i] = x$ ，平均情况和最坏情况都需要检查 $n$ 个元素。

8. SCRAMBLE-SEARCH 的运行时间等于随机变换排列输入数组所需要的时间加上 DETERMINSTIC-SEARCH 的运行时间， DETERMINSTIC-SEARCH 的运行时间见上面的第 5 到 7 问。

9. 假设我们使用 RANDOM-IN-PLACE 算法（见第4讲PPT第19页）来在 SCRAMBLE-SEARCH 中打乱数组，时间为 $\Theta(n)$ （假设随机数生成器是常数时间）。

比较上述三种搜索算法在有 $k$ 个元素等于 $x$ 时，平均和最坏情况下的运行时间或者期望运行时间（用基本操作的次数来表示），以及找不到时的运行时间：

其中， $(n + 1) / (k + 1) \le n / k \Leftrightarrow k \le n$ ，因此我选择 DETERMINSTIC-SEARCH ，因为它三种情况下时间都是最短的。

最坏情况下三种算法都是倒霉地把不是 $x$ 的全部尝试完毕后再找到 $x$ ，其中 RANDOM-SEARCH 更惨，还会重复尝试已经尝试过的位置。