求“公共数”的算法

Question

让一个大小为n的数组。我们需要编写一个算法来检查是否有至少出现n/loglogn次数的数字。

我知道在O(n*logloglogn)中有一种方法可以这样做：

1. 使用select算法查找中间值，并计算它出现的次数。如果它看起来比n/loglogn更多，我们就返回true。这需要O(n)。
2. 根据中间值对数组进行分区。它需要O(n)
3. 将该算法应用于分区的两边(两个n/2数组)。
4. 如果我们到达一个小于n/loglogn大小的子数组，停止并返回false。

问题：

1. 这个算法正确吗？
2. 递归是：T(n) = 2T(n/2) + O(n)，基本情况是T(n/loglogn) = O(1)。现在，递归树中最大的调用数是O(logloglogn)，因为每个调用都是O(n)，所以时间复杂度是O(n*logloglogn)。对吗？

Answer 1

建议的解决方案可以工作，其复杂性实际上是O(n/logloglog(n))。

假设"pass i“是深度i的所有递归调用的运行。请注意，每次传递都需要O(n)时间，因为每个调用都比O(n)少得多，但是有几个调用--总的来说，每个元素在每个" pass“中处理一次。

现在，我们需要找到通行证的数量。这是通过求解方程来实现的：

n/log(log(n))  = n / 2^x
<->
n/log(log(n)) * 2^x = n 

其思想是，每个调用将数组除以一半，直到达到预定义的n/log(log(n))大小。

这个问题在O(n/log(log(log(n)))中作为你可以在wolfram alpha中看到，在x中确实得到了解决，因此复杂性实际上是O(nlog(log(log(n))))。

至于正确性--这是因为如果一个元素重复的次数比所需的多--它必须在某个子数组中，其大小大于/等于所需的大小，并且通过不断缩小数组的大小，您将到达#repeats <= size(array) <= #repeats的某个点--此时，您将找到这个元素的中间值，并发现它确实是一个“频繁项”。

其他一些方法，在O(n/log(log(n))时间--但具有很大的常数是由卡普-帕帕迪米特里欧-尚克建议的，并且是基于在处理数组时用“候选”填充表的方法。