"Find the element repeated more than n/2 times" 使用随机的最坏情况运行时间
Worst case runtime for "Find the element repeated more than n/2 times" using random
有问题"Find the element repeated more than n/2 times"
能否请您帮助估计使用随机的解决方案的时间复杂度：
- 在数组中选择随机元素
- 遍历数组并计算所选元素的出现次数
- 如果计数 > N/2 - return 那个元素。
- 从第 1 步开始重复。
如果我使用给出随机统一数的完美随机生成器，这种方法最坏的情况是什么？ O(N²)?
我的直觉告诉我，平均来说它应该在两次尝试中给出答案，但这只是平均情况。如何证明？我不太确定如何估计 运行 随机算法的时间。
假设实际有一个元素出现次数超过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，这个数字小于宇宙中原子数的一倍。因此，即使您不能限制最坏情况下的运行时间，但从天文数字的角度来看，这种可能性很小，您可以安全地忽略它。
希望对您有所帮助！
对于随机算法，预期的 运行 时间更好地表征了它们的 运行 时间。对于您描述的算法，预期的 运行 时间最多为
S = n * 1/2 + 2n * 1/2^2 + 3n * 1/2^3 + ... up to infinity
我们可以这样解决：
S = n/2 + 2n/2^2 + 3n/2^3 + ... up to infinity
2S = n + 2n/2 + 3n/2^2 + 4n/2^3 + ... up to infinity
(subtracting the top from bottom)
S = n + n/2 + n/4 + n/8 + ... up to infinity
= 2n
所以预期的运行时间是O(n)。
如果我们谈论最坏情况复杂性，我们指的是输入的最坏情况，即强制输入的输入算法进入最糟糕的 运行 时间。
随机算法也是如此。我们计算最坏情况输入的预期复杂度。
在您的示例中，最糟糕的输入是长度为 n 的数组，它仅包含数字 a ⌊n/2⌋+1 次。
复杂度现在是 O(n)⋅<b>E</b>[X]，其中 X 是尝试次数你必须从数组中随机选择一个数字，直到你选择 a。
如果 a 是数组中的 m 次 <b>E</b>[X] = n/m 成立。所以对于我们最坏的情况输入，我们得到 <b>E</b>[X] = n/(⌊n/2⌋+1) < n/(n/2 ) = 2.
所以这个随机算法的最坏情况复杂度为 O(n)。
该算法的最坏情况 运行 时间没有界限。
"perfect" 随机数生成器的输出不能取决于以前的历史；否则它将是不完美的（现实世界的伪 rng 以这种方式是不完美的，因此您可以为特定的 PRNG 构建一个真实的边界）。
因此，在 RNG 猜测多数元素的位置之一之前，它可能需要任意次数的猜测。
如果您被允许重新排列数组，您可以将错误的猜测交换到数组的（仍然未知的）部分的开头，然后将猜测限制在尚未猜到的位置。这会将迭代次数限制为 n/2-1，因此算法的最坏情况 运行 时间为 O(n2)。
虽然它对 big-O 运行时没有影响，但您几乎总是可以提前停止计数扫描，因为您已经找到 n/2+1 个元素，或者因为没有足够的未扫描元素离开使计数达到该阈值。即使进行了这种优化，单次扫描的最坏情况（交替元素）时间仍然是 n，预期扫描仍然是 O(n)。
有问题"Find the element repeated more than n/2 times"
能否请您帮助估计使用随机的解决方案的时间复杂度：
- 在数组中选择随机元素
- 遍历数组并计算所选元素的出现次数
- 如果计数 > N/2 - return 那个元素。
- 从第 1 步开始重复。
如果我使用给出随机统一数的完美随机生成器，这种方法最坏的情况是什么？ O(N²)?
我的直觉告诉我，平均来说它应该在两次尝试中给出答案，但这只是平均情况。如何证明？我不太确定如何估计 运行 随机算法的时间。
假设实际有一个元素出现次数超过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，这个数字小于宇宙中原子数的一倍。因此，即使您不能限制最坏情况下的运行时间，但从天文数字的角度来看，这种可能性很小，您可以安全地忽略它。
希望对您有所帮助！
对于随机算法，预期的 运行 时间更好地表征了它们的 运行 时间。对于您描述的算法，预期的 运行 时间最多为
S = n * 1/2 + 2n * 1/2^2 + 3n * 1/2^3 + ... up to infinity
我们可以这样解决：
S = n/2 + 2n/2^2 + 3n/2^3 + ... up to infinity
2S = n + 2n/2 + 3n/2^2 + 4n/2^3 + ... up to infinity
(subtracting the top from bottom)
S = n + n/2 + n/4 + n/8 + ... up to infinity
= 2n
所以预期的运行时间是O(n)。
如果我们谈论最坏情况复杂性，我们指的是输入的最坏情况，即强制输入的输入算法进入最糟糕的 运行 时间。
随机算法也是如此。我们计算最坏情况输入的预期复杂度。
在您的示例中，最糟糕的输入是长度为 n 的数组，它仅包含数字 a ⌊n/2⌋+1 次。
复杂度现在是 O(n)⋅<b>E</b>[X]，其中 X 是尝试次数你必须从数组中随机选择一个数字，直到你选择 a。
如果 a 是数组中的 m 次 <b>E</b>[X] = n/m 成立。所以对于我们最坏的情况输入，我们得到 <b>E</b>[X] = n/(⌊n/2⌋+1) < n/(n/2 ) = 2.
所以这个随机算法的最坏情况复杂度为 O(n)。
该算法的最坏情况 运行 时间没有界限。
"perfect" 随机数生成器的输出不能取决于以前的历史；否则它将是不完美的（现实世界的伪 rng 以这种方式是不完美的，因此您可以为特定的 PRNG 构建一个真实的边界）。
因此，在 RNG 猜测多数元素的位置之一之前，它可能需要任意次数的猜测。
如果您被允许重新排列数组，您可以将错误的猜测交换到数组的（仍然未知的）部分的开头，然后将猜测限制在尚未猜到的位置。这会将迭代次数限制为 n/2-1，因此算法的最坏情况 运行 时间为 O(n2)。
虽然它对 big-O 运行时没有影响，但您几乎总是可以提前停止计数扫描，因为您已经找到 n/2+1 个元素，或者因为没有足够的未扫描元素离开使计数达到该阈值。即使进行了这种优化，单次扫描的最坏情况（交替元素）时间仍然是 n，预期扫描仍然是 O(n)。