algorithm - 是否有一种算法可以在线性时间内找到 log(n) 顺序统计信息

Question

我可以构建一个算法 FindStats(A,k)

它接收一个大小为 n 的输入数组 A 和一个整数 k，使得 2^k <= n(这意味着 k 在最坏情况下为 log(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 阶统计量，则找到第1， 2nd, 4th, 8th..., 2^kth 也可以在 O(n) 时间内实现。这是由于简单的代数:

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) 解决方案。