算法导论5.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 953 阅读时长 ≈ 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)\)。