随机化算法的运行时间来查找数组中的多数元素？

Question

这是针对 leetcode 问题 169. 多数元素。给定一个数字数组，保证数组中存在一个大于下限（n/2）的数字，可以通过选择随机索引并检查它的值是否是多数元素来找到这样的数字或没有，然后重复直到找到为止。这是提供的解决方案之一。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        majority_count = len(nums)//2

        while True:
            candidate = random.choice(nums)
            if sum(1 for elem in nums if elem == candidate) > majority_count:
                return candidate

我感到困惑的是这个算法的运行时分析，它基于这样的断言：由于多数元素总是保证占据数组的一半以上，所以应用于我们场景的这个算法总是比 if 更快它适用于仅存在一个元素恰好占据数组一半的情况。因此，预期迭代次数 EV_(itersprob) 可以表示为小于或等于修改场景的预期迭代次数 EV_(itersmod)

我感到困惑的是这个系列是如何针对这个问题组合在一起的。变量 i 是迭代次数，但为什么要对 (i * (1/2^i)) 求和？

基本上，while 循环迭代次数的运行时间预计是恒定的，使得整个算法的运行时间是线性的（由于内部循环每次运行 n 次）

Answer 1

我们在第一次运行中猜出正确元素的概率是

p = 1/2

。

我们在第二次运行中猜对正确元素的概率是：我们在第一次运行中猜错了，但在第二次运行中猜对了。所以，

q * p = 1/2 * 1/2 = 1/4

。

我们在第三次运行中猜出正确元素的概率是：我们在第一次运行中猜错了，在第二次运行中猜错了，但在第三次运行中猜对了。所以，

q * q * p = 1/2 * 1/2 * 1/2 = 1/8

。

因此，预期的运行次数是：

1 * 1/2 + 2 * 1/4 + 3 * 1/8 + ...

。正如公式所示。

之后，我们可以直观地注意到，如果概率

p > 1/2

，预期的时间会更少。

Answer 2

期望值是

i * p(i)

的总和，其中

p(i)

是结果的概率

i

/

算法精确执行一次迭代的概率是 1/2。它恰好执行两次迭代的概率是

1/2 * 1/2

：在第一次迭代中我们选择了错误的候选者，在第二次迭代中我们选择了正确的候选者。一般来说，它精确执行

i

次迭代的概率是

1/2 ** i

：

i - 1

错误选择，然后是正确选择。

总和如下。