Problem 1 (教材习题 5-1)
(概率计数) 利用一个 b 位的计数器,我们一般只能计数到 2b−1 。而用 R.Morris 的 概率计数法 ,我们可以计数到一个大得多的值,代价是精度有所损失。
对 i=0,1,⋯,2b−1 ,令计数器值 i 表示 ni 的计数,其中 ni 构成了一个非负的递增序列。假设计数器初值为 0 ,表示计数 n0=0 。 INCREMENT 运算单元工作在一个计数器上,它以概率的方式包含值 i 。如果 i=2b−1 ,则该运算单元报告溢出错误;否则, INCREMENT 运算单元以概率 1/(ni+1−ni) 把计数器增加 1 ,以概率 1−1/(ni+1−ni) 保持计数器不变。
对所有的 i≥0 ,若选择 ni=i ,此计数器就是一个普通的计数器。若选择 ni=2i−1(i>0) ,或者 ni=Fi (第 i 个佩波那契数,参见作业3问题2),则会出现更多有趣的情形。
对于这个问题,假设 n2b−1 已经足够大,发生一个溢出错误的概率可以忽略。
请说明在执行 n 次 INCREMENT 操作后,计数器所表示的数期望值正好是 n 。
分析计数器表示的计数的方差依赖于 ni 序列。我们来看一个简单情形:对所有 i≥0 , ni=100i 。在执行了 n 次 INCREMENT 操作后,请估计计数器所表示数的方差。
Solution
我们只需要证明在执行 1 次 INCREMENT 操作后,计数器所表示的数期望值正好是 1 即可。
假设当前计数器的值为 i ,则其代表的数值为 ni ,将其代表的数值 j 从 ni 增加到 ni+1 时,每次都会有 1/(ni+1−ni) 的概率使得计数器的值加1,记增值为 Xni ,则 E[Xni]=1/(ni+1−ni) 。
记这次 INCREMENT 操作总的增值为 X ,则 X=∑j=nini+1Xj 。于是
E[X]=E[j=ni∑ni+1Xj]=j=ni∑ni+1E[Xj]=j=ni∑ni+1ni+1−ni1=ni+1−nini+1−ni=1
当 ni=100i 时,ni+1−ni=100 为定值,于是,每次 INCREMENT 会有 100 次其代表数值的变化,每次概率为 p=1/100 。在执行了 n 次 INCREMENT 之后,记增值为 Y ,Y 的大小就是 100n 次代表数值的变化中使得计数器值增加 1 的次数。
- 于是 Y∼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 中的每一个元素。注意,我们每次都是从全部下标的集合中挑选,于是可能会不止一次地检查某个元素。
请写出过程 RANDOM-SEARCH 的伪代码来实现上述策略。确保当 A 中所有下标都挑选过时,你的算法应停止。
假定恰好有一个下标 i 使得 A[i]=x 。在我们找到 x 和 RANDOM-SEARCH 结束之前,必须挑选 A 下标的数目期望是多少?
假设有 k≥1 个下标 i 使得 A[i]=x ,推广你对第2问的解答。在找到 x 或 RANDOM-SEARCH 结束之前,必须挑选 A 下标的数目期望是多少?你的答案应该是 n 和 k 的函数。
假设没有下标 i 使得 A[i]=x 。在检查完 A 的所有元素或 RANDOM-SEARCH 结束之前,我们必须挑选的 A 的下标的数目期望是多少?
现在考虑一个确定性的线性查找算法,我们称之为 DETERMINSTIC-SEARCH 。具体地说,这个算法在 A 中顺序查找 x ,考虑 A[1],A[2],A[3],⋯,A[n] ,直到找到 A[i]=x ,或者到达数组的末尾。假设输入数组的所有排列都是等可能的。
假设恰好有一个下标 i 使得 A[i]=x 。 DETERMINSTIC-SEARCH 平均情形的运行时间是多少? DETERMINSTIC-SEARCH 最坏情况的运行时间又是多少?
假设有 k≥1 个下标 i 使得 A[i]=x ,推广你对第5问的解答。 DETERMINSTIC-SEARCH 平均情形的运行时间是多少? DETERMINSTIC-SEARCH 最坏情形的运行时间又是多少?你的答案应该是 n 与 k 的函数。
假设没有下标 i 使得 A[i]=x 。 DETERMINSTIC-SEARCH 平均情形的运行时间是多少? DETERMINSTIC-SEARCH 最坏情形的运行时间又是多少?
最后,考虑一个随机算法 SCRAMBLE-SEARCH ,它先将输入数组随机变换排列,然后在排列变换后的数组上,运行上面的确定性线性查找算法。
设 k 是满足 A[i]=x 的下标的数目,请给出在 k=0 和 k=1 情况下,算法 SCRAMBLE-SEARCH 最坏情况的运行时间和运行时间期望。推广你的解答以处理 k≥1 的情况。
你将会使用 3 种查找算法中的哪一个?解释你的答案。
Solution
- 算法伪代码如下:
其中,数组 P 用于标记每个下标是否都已经被判断过。
假设需要挑选 X 次才能挑选到使得 A[i]=x 的 i ,每次都有 1/n 的概率可以选到,于是 X∼g(1/n) ,由几何分布的期望公式有 E[X]=n 。
假设需要挑选 X 次才能挑选到使得 A[i]=x 的 i ,每次都有 k/n 的概率可以选到,于是 X∼g(k/n) ,由几何分布的期望公式有 E[X]=n/k 。
相当于球与箱子的问题。往 b 个箱子里面连续随机扔球,在期望每个箱子都有球之前,大约需要投 blnb 次,具体见第4讲PPT第24-25页。所以我们必须挑选的下标的数目期望为 nlnn 。
考虑需要检查的元素个数来作为运行时间的考量标准。
记需要检查的元素个数为 X ,则 X=i 相当于 A[i]=x ,而 A 是随机排列的且其中只有 1 个 x ,于是 Pr{X=i}=1/n ,其中 i=1,2,...,n 。根据期望定义,有
E[X]=i=1∑ni⋅Pr{X=i}=i=1∑nni=2n+1
最坏情况为 A[n]=x 的时候,需要检查全部 n 个元素。
- 依旧考虑需要检查的元素个数来作为运行时间的考量标准。
记第 i 个元素被检查为事件 Hi , Xi=I{Hi} ,则 E[Xi]=Pr{Hi}。
当 A[i]=x 时, 第 i 个元素被检查说明所有的 A[aj]=x(j=1,2,...,k) 都满足 aj>i ,否则 i 就会被检查了;也就是说在 a1,a2,...,ak,i 这 k+1 个元素组成的排列中 i 得排在第一个(其他元素无所谓),因此 Pr{Hi}=1/(k+1) 。
当 A[i]=x 时,第 i 个元素被检查说明在这 k 个值为 x 的数组成的排列中, i 得是第一个,因此 Pr{Hi}=1/k 。
记所有等于 x 的元素组成的集合为 S , ∣S∣=k ,所有被检查的元素个数为 X , X=∑i=1nXi ,所以
E[X]=E[i=1∑nXi]=i=1∑nE[Xi]=i=1∑nPr{Hi}=i∈/S∑Pr{Hi}+i∈S∑Pr{Hi}=k+1n−k+kk=k+1n+1
因此,DETERMINSTIC-SEARCH 平均情况下需要检查 (n+1)/(k+1) 个元素。
最坏情况是显然的,就是 k 个 x 恰好是最后 k 个元素,需要检查 n−k+1 个元素。
需要检查所有元素才能确认不存在 A[i]=x ,平均情况和最坏情况都需要检查 n 个元素。
SCRAMBLE-SEARCH 的运行时间等于随机变换排列输入数组所需要的时间加上 DETERMINSTIC-SEARCH 的运行时间, DETERMINSTIC-SEARCH 的运行时间见上面的第 5 到 7 问。
假设我们使用 RANDOM-IN-PLACE 算法(见第4讲PPT第19页)来在 SCRAMBLE-SEARCH 中打乱数组,时间为 Θ(n) (假设随机数生成器是常数时间)。
比较上述三种搜索算法在有 k 个元素等于 x 时,平均和最坏情况下的运行时间或者期望运行时间(用基本操作的次数来表示),以及找不到时的运行时间:
|
平均情况 |
最坏情况 |
找不到时 |
RANDOM-SEARCH |
n/k |
Ω(n−k+1) |
nlnn |
DETERMINSTIC-SEARCH |
(n+1)/(k+1) |
n−k+1 |
n |
SCRAMBLE-SEARCH |
(n+1)/(k+1)+Θ(n) |
n−k+1 |
n |
其中, (n+1)/(k+1)≤n/k⇔k≤n ,因此我选择 DETERMINSTIC-SEARCH ,因为它三种情况下时间都是最短的。
最坏情况下三种算法都是倒霉地把不是 x 的全部尝试完毕后再找到 x ,其中 RANDOM-SEARCH 更惨,还会重复尝试已经尝试过的位置。