arrays - 拉斯维加斯算法运行时分析

Question

在 n 个元素的数组中，如果 n/2 是重复元素，其余元素不同，我们可以使用 Las Vegas 算法在 o(logn) 时间内得到重复元素。

还有另一个问题说：使这个算法o（logn）即（n / k重复元素，其中k =？）所需的最小重复次数是多少，如果重复元素是root（n），运行时间是多少？

我的结果表明，如果重复元素是 root(n)，则它不是 o(logn)，但我无法使用 Las Vegas 算法找到这个问题的松散界限。帮助将不胜感激。

Answer 1

“拉斯维加斯”不是算法；这是一种算法。显而易见的算法是随机均匀地对元素对进行采样，直到它们匹配。当数组中有一个元素重复 n/2 次时，每对的成功概率为 ((n/2)/n)((n/2-1)/(n-1)) = 1/4 - O (1/n)，因此预期的运行时间是 1/(1/4 - O(1/n)) = 4 + O(1/n) = O(1) 个采样对。

由于这可能是家庭作业，因此您要弄清楚如何针对不同的重复次数调整分析。