查找是否存在 "common number" 的算法

Question

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

我知道在 O(n*logloglogn) 中有一种方法是这样的：

使用 select 算法找到中位数并计算它出现的次数。如果它出现超过 n/loglogn 我们 return true。需要 O(n).
根据中位数对数组进行分区。需要 O(n)
在分区的两侧（两个 n/2 数组）应用算法。
如果我们到达的子数组大小小于 n/loglogn，则停止并 return false。

问题：

这个算法正确吗？
递归是：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".[=22 中处理一次=]

现在，我们需要找出通过的次数。这是通过求解方程式完成的：

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

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

对于O(n/log(log(log(n)))中的x确实解决了这个问题，如you can see in wolfram alpha，因此复杂度确实是O(nlog(log(log(n))))

至于正确性 - 那是因为如果一个元素的重复次数超过要求 - 它必须在某个子数组中，其大小为 greater/equals 所需的大小，并且通过不断减小数组的大小，您将到达对于 #repeats <= size(array) <= #repeats 的某个点的情况 - 在这一点上，您将找到这个元素作为中位数，并发现它确实是 "frequent item".

一些其他的方法，在 O(n/log(log(n)) 时间内 - 但是 Karp-Papadimitriou-Shanker 建议具有很大的常量，并且基于在处理数组。

查找是否存在 "common number" 的算法

Algorithm for finding if there's a "common number"

arrays

algorithm

data-structures