algorithm - 是否有一种算法可以在线性时间内查找 log(n) 顺序统计信息
问题描述
我可以建立一个算法 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) 的结果。
我可以改进它吗?甚至有可能实现它吗?
解决方案
我认为吉姆米歇尔的回答是应用类似的逻辑。我不确定为什么该答案被删除。
如果我们承认有任何选择算法可以及时保证单k
次统计O(n)
,那么及时找到1st, 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.)
另一个让我感兴趣的想法是,我们是否可以以某种方式使用 heapifying 方法来保证所有表亲都小于下一层的表亲。足够有效地执行此操作还可以保证使用广度优先搜索遍历此特殊堆的每个级别的 O(n) 解决方案。
推荐阅读
- php - 在 OS X 11.3.1 上构建最新的 PHP 8.0.6+ 时,“配置 opcache 时未找到支持的共享内存缓存支持”
- python - 如何将迭代公式翻译成 Python
- python - python脚本无法在heroku上托管的其他python脚本中调用fn
- python - 读取文本文件中的多行
- excel - 自动填充功能问题
- c - 我无法理解我的 C 程序中的逻辑
- google-cloud-platform - 权限 GCS 存储桶
- powershell - 如何将任何密钥传递给powershell Start-Process msiexec.exe 命令
- python - 检查 2 个 CSV 中的相同 ID 是否具有不同的名称
- typescript - 运算符 '*=' 不能应用于类型 'number | bigint' 和 '数字'。",