其中Add,Get kth最大的数据结构是O(log n)和O(1)

Question

给出一个存储可比较对象和支持add()与get(k)操作get(k)的数据结构[ 返回数据结构中第k个最小元素(1 <= k <= n)].get(k)必须是O(1)且add()必须是O(log n)n是添加到数据结构的对象数.再举结构,其中get(k)的O(log n)和补充的是O(1)

Answer 1

无法使用分摊 O(1) 时间添加和最坏情况 O(log n) 时间获取来构建基于确定性比较的数据结构。信息论下界不能排除其他配置，但我严重怀疑有人知道如何做到这一点。

\n\n

^{对于专家来说：对手首先添加 n 个项目，以留下大小至少为 log 2} n的反链的方式回答算法的 O(n) 比较。然后，它以计算 get(k) 的方式选择 k，迫使算法在反链上进行选择，从而产生 \xce\xa9(log ² n) 的成本。

\n\n

为什么对手能够强行推出这么大的反链？假设该算法始终不留下超过 log ² n 个元素的反链。根据迪尔沃斯定理，元素最多可以划分为 log ² n 条链，这些链可以使用 O(n log log n) 次比较进行合并，从而给出使用 o(n log n) 次比较的排序算法，从而产生矛盾。

\n\n

你的面试官的意思是什么？我可以想象，如果这两项操作都被摊销，那么就有一个解决方案。然而，这是对要求的非规范放宽。

\n