算法导论5.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 893 阅读时长 ≈ 1 分钟

5.1-1

如果我们可以确定排名最高的某个候选人；那么去掉这个人后，我们依旧可以确定出当前排名最高的某个候选人（也就是次高）……一直去掉最后一个人之后，那么就可以得到这些候选人的排名。

由于这种好的关系具有传递性，因此可以确定出这一些候选人的全序关系。

$\star$ 5.1-2

1
2
3
4
5
6
7
8
9
10
11
RANDOM(a, b)
  r = b - a + 1
  // beta是r的比特数。
  beta = ceil(log(2, r))
  while True
    s = 0
    for i = 0 to beta
      t = RANDOM(0, 1)
      s = (s << 1) | t
    if s < r
      return s + a

从RANDOM(a, b)中获取随机数，相当于从a + RANDOM(0, b - a)中获取随机数。令$r=b-a+1,\beta=\lceil\lg r\rceil$。考虑生成一个$\beta$比特数$s$，如果$s< r$，那么返回$s+a$，否则重复进行即可。

那么，生成一个小于$r$的$\beta$比特数的概率为$\dfrac{r}{2^\beta}=2^{\lg r-\lceil\lg r\rceil}>\dfrac{1}{2}$。

可以发现第4行的while循环运行次数服从参数为$\dfrac{r}{2^\beta}$的指数分布，因此其期望运行次数为$\dfrac{2^\beta}{r}$。那么，RANDOM(0, 1)的被调用期望次数为$\beta\cdot \dfrac{2^\beta}{r}<2\beta$。因此RANDOM(a, b)的时间复杂度为$O(\lg(b-a))$。

$\star$ 5.1-3

1
2
3
4
5
6
RANDOM()
  while True
    x = BIASED-RANDOM()
    y = BIASED-RANDOM()
    if x != y
      return x

在单次循环中，考虑两次调用BIASED-RANDOM()，其结果分别为$x,y$。可以发现一共有$4$种结果，分别为$00,01,10,11$，那么接下来进行的操作如下：

  • $00$，继续进行下一次循环。
  • $01$，返回$0$。
  • $10$，返回$1$。
  • $11$，继续进行下一次循环。

这里用到的是输出$01$和$10$的概率都是$p(1-p)$。

将这两部分的概率值相加，可以发现这个while循环运行次数服从参数为$2p(1-p)$的指数分布，因此其期望运行次数为$\dfrac{1}{2p(1-p)}$。那么，BIASED-RANDOM的被调用期望次数为$\dfrac{1}{p(1-p)}$。因此RANDOM的时间复杂度为$\Theta\left(\dfrac{1}{p(1-p)}\right)$。