algorithm - "Find the element repeated more than n/2 times"使用随机的最坏情况运行时间

Question

有问题"Find the element repeated more than n/2 times"

能否请您帮助估计使用随机解决方案的时间复杂度:

1. 随机选择数组中的元素
2. 遍历数组并计算所选元素出现的次数
3. 如果计数 > N/2 - 返回该元素。
4. 从第 1 步开始重复。

如果我使用给出随机统一数的完美随机生成器，这种方法最坏的情况是什么？ O(N²)?

我的直觉告诉我，平均来说它应该在两次尝试后给出答案，但这只是平均情况。如何证明？我不太确定如何估计随机算法的运行时间。

Answer 1

假设实际有一个元素出现次数超过n/2次，则预期运行时间为O(n)。你可以这样想——每次你选择一个元素，你需要做 O(n) 的工作来检查它是否是多数元素。接下来的问题是，根据预期，您将不得不选择多少元素。每次你随机选择一个元素时，你至少有 1/2 的概率选择了多数元素。按照预期，这意味着您需要在找到多数元素之前选择两个元素，因此运行时间将为 O(n)。如果你很好奇为什么，请注意恰好 k 个探测(k > 0)之后你找到你正在寻找的东西的概率最多为 2^-k，因为你需要有第一个k - 1 次探测未成功，然后让第 k 次探测成功。然后您可以将预期值计算为

0 * 2^-0 + 1 * 2^-1 + 2 * 2^-2 + ...

= 2

(已知这个求和正好可以计算出两个，尽管证明它有点困惑。)

不过，在最坏的情况下，每次选择一个元素时，您都会选择一个不是多数元素的元素。不过，这是极不可能的 - 在 k 轮之后找不到多数元素的概率最多为 2^-k。对于 k = 300，这个数字小于宇宙中原子数的一倍。因此，即使您不能限制最坏情况下的运行时，它在天文数字上的可能性很小，您可以安全地忽略它。

希望这对您有所帮助!