有没有在线性时间内找到log(n)顺序统计量的算法？

Question

我能构建一个算法FindStats(A，k)吗？

它接收大小为n的输入数组A和整数k，使得2^klog(N)(这意味着k在最坏情况下为<= (N))并输出A的1,2,4,8，...,2^k顺序统计量。所有这些都在线性时间内完成！

到目前为止，我尝试了什么：

我知道有一个算法QuickSelect(A，k) (确定性算法)，它在线性时间内返回k‘阶统计量，但在我的例子中，平凡的解决方案是遍历所有1,2,4,8...,2^k个顺序统计量并返回结果为O(nlogn)。

我能改进它吗？有没有可能实现它呢？

Answer 1

我认为Jim Mischel的答案是应用了类似的逻辑。我不确定为什么这个答案被删除了。

如果我们承认有任何选择算法可以在O(n)时间内保证单个k个顺序统计量，那么在O(n)时间内也可以找到1st, 2nd, 4th, 8th..., 2^kth。这是由于简单的代数：

let a = 2^k
then the sequence,
  a + 1/2*a + 1/4*a + 1/8*a + 1/16*a ...
converges and can never exceed 2*a

这意味着如果在每次选择之后(或期间)，我们将列表划分为一半大小的部分，并将其作为下一次选择的输入，则我们传递给选择算法的总输入永远不会超过O(n)。我们的时间计算如下所示：

find 2^kth:       n
find 1/2 * 2^kth: 2^k
find 1/4 * 2^kth: 2^(k-1)
find 1/8 * 2^kth: 2^(k-2)
...

The sum on the right cannot exceed
n + 2^(k + 1)
=> O(n + 2^(log2(n) + 1))
=> O(n)

(If it takes an extra traversal to
 partition the list after each selection,
 the summation could add another n,
 not affecting the general complexity.)

另一个让我感兴趣的想法是，我们是否可以以某种方式使用堆积方法来确保所有的表亲都比下一级的表亲更小。这样做的效率足够高，也可以保证使用广度优先搜索遍历这个特殊堆的每个级别的O(n)解。