LeetCode 169多数元素随机化算法时间复杂度分析疑问

算法概述 #

这是LeetCode 169. 多数元素问题的官方随机化解法之一。题目保证数组中存在出现次数大于floor(n/2)的元素，算法逻辑很直接：随机选数组中的元素当候选，验证它是不是多数元素，重复这个过程直到找到目标元素。

对应的Python代码如下：

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

时间复杂度推导解惑 #

为什么会出现Σ(i*(1/2^i))的求和？ #

这个求和是针对元素占比恰好为1/2的极端场景（也就是你提到的EV_(itersmod)）来推导的，逻辑是这样的：

• 当多数元素占比刚好1/2时，每次随机选中它的概率p=1/2，选不中的概率也是1/2。
• 迭代次数为i意味着：前i-1次全选到了非多数元素，第i次才选中目标。这个事件发生的概率是(1/2)^(i-1) * (1/2) = 1/2^i。
• 根据期望的定义，迭代次数的期望就是所有可能的迭代次数乘以对应概率的总和，也就是EV = Σ(i * P(迭代i次成功))，代入概率后就得到了Σ(i*(1/2^i))（i从1到无穷大）。

原问题的期望迭代次数为何更小？ #

原问题中多数元素占比p > 1/2，比如占比是k/n（k > n/2），那每次选中它的概率就是p = k/n > 1/2。对于这种单次成功概率为p的独立重复试验，迭代次数服从几何分布，它的期望是1/p。
因为p > 1/2，所以1/p < 2；而极端场景p=1/2时，Σ(i*(1/2^i))的求和结果是2（用错位相减法就能算出来），所以原问题的期望迭代次数EV_(itersprob)肯定小于等于2，确实比极端场景更快。

整体时间复杂度为何是线性？ #

每次迭代内部需要遍历整个数组验证候选元素，这一步的时间复杂度是O(n)；而期望迭代次数是个常数（最多也就2次），所以整体时间复杂度是O(n * 常数) = O(n)，也就是线性时间。

内容的提问来源于stack exchange，提问作者Shisui