概率算法

Probabilistic algorithm

我们得到一个二进制数组，它有 n 个零 或 floor(n/2) 个零 和 天花板（n/2）一个.

我们要判断数组是否包含1。

问。建议一个时间复杂度为 O(1) 的随机算法，并以至少 3/4 的概率给出正确答案。该算法可以给出错误答案，但不会超过 1/4 的可能输入。

我想就如何解决这个问题获得一些指导。

检查数组中的随机项：

  1. 如果item == 0 return第一种可能性(n个零)
  2. 如果item == 1 return第二种可能性（n/2零和n/2一）

让我们看看发生了什么：给出错误答案的唯一可能性是我们有第二种可能性， 但是我们得到 item == 0 并且答案是 第一种可能性 。条件（第二种可能性）概率是

p = 1/2

如果我们检查两个个随机项目

p = 1/4 (two items are zeroes)

如果我们检查 三个 个随机项目

p = 1/8 (three items are zeroes)

现在，让我们计算错误答案的贝叶斯概率，让

P0 - probability of the 1st (all zeroes) outcome
P1 - probability of the 2nd (half zeroes, half ones) outcome

Perror = P1 * p / (P0 + P1) <= 1/4

或

P1 * p / (P0 + P1) <= 1/4

p <= (P0 + P1) / 4 / P1

p <= P0 / (4 * P1) + 1/4

从最坏的情况，P0 = 0 (P1 = 1) 我们得到条件 p:

p <= 1/4

到目前为止一切顺利，我们应该检查 两个随机 数组的项目，然后

  • 如果两个项都是0，我们回答“全零的情况”
  • 如果 任何 项目是 1，我们回答“半个零，半个一”