设计一个中间O(1)、访问时间O(log k)的数据结构

Question

我正在设计一个具有以下功能和约束的数据结构：

1. init()

   ，时间复杂度为 O(1)：空结构的初始化。

2. push(x)

   ，时间复杂度为 O(1)：将键为 x 的新元素插入到结构中。

3. pop()

   ，时间复杂度为O(1)：删除最后插入到结构中的元素。

4. getMiddle()

   ，时间复杂度为 O(1)：返回中间 (n/2) 元素的键（按插入顺序）。

5. getAt(k)

   ，时间复杂度为 O(log k)：返回第 k^th 元素的键（按插入顺序）。

空间复杂度为 O(n)，当 n 是结构中元素的数量时。

我可以使用以下结构：ADT、队列、堆栈、数组、链表、二叉树和二叉搜索树。

我最初的想法：

我考虑使用链表，因为： 初始化是 O(1)。 push(x) 和 pop() 操作都是 O(1)。

对于 getMiddle()，我考虑维护一个指向中间元素的指针。该指针在每次插入或删除过程中都会适当移动，因此返回中间元素的时间复杂度为 O(1)。

但是，我的主要挑战在于 getAt(k) 操作。 我需要达到 O(log k) 时间复杂度，但是：

1. 简单地遍历链表需要 O(k)，这太慢了。

2. 我想过执行二分搜索，但这需要 O(log n)，而我需要 O(log k)。

3. 我还考虑过在第 k 个元素处拆分列表，但我不确定如何有效地实现这一点。

请求帮助： 您是否有建议或替代方法来在 O(log k) 中实现 getAt(k) 同时满足其他约束？我将不胜感激有关此问题的任何见解或指导。

Answer 1

有趣的问题！

如果您需要在“摊销”意义上满足所有这些时间界限，则动态数组支持在时间 O(1) 内进行随机访问，并支持在摊销时间 O(1) 内追加元素和从列表末尾删除元素。那将满足您的所有要求。这可能是最简单的选择。 如果您需要在“最坏情况”意义上满足所有这些要求，我能想到的唯一满足边界的数据选项是“可扩展数组”数据结构，它本质上是动态数组的去摊销版本大批。这可以由两个数组构建，但假设您可以在 O(1) 时间内分配大小为 n 的内存块。

我一直在考虑其他选择，看看是否有更简单的方法，但我尝试过的都没有成功。例如，跳跃列表可让您获得第 k 个元素的（预期情况）O(log k) 查找。为此，请从底层开始向上移动，直到到达超过第 k 个位置的元素，然后从该级别或该级别以下开始执行常规跳跃列表查找。这个想法是，平均而言，第一次超过位置 k 时，您将处于大约 2k 的位置，并且在该子跳列表中进行搜索将花费时间 O(log 2k) = O(log k) 来找到什么你正在寻找。 这种方法有两个问题。第一个是跳跃列表是随机的，尽管可以通过使用跳跃列表的确定性版本来克服这个问题（这些存在，尽管它们不那么出名）。第二个是，由于连接适当指针的成本，插入跳表的成本不是 O(1)。您可以证明，如果您使用确定性方案，则插入此类跳跃列表的摊销成本将为 O(1)，但如果您要追求摊销效率，则应该使用动态数组。

我考虑的另一个选项是类似 VList 的东西 - 元素块的链接列表，其大小随着您的前进而呈指数级增长。然后，只需在链表中向前移动，直到找到适当大小的块，然后在该块内查找，即可在 O(log k) 时间内找到第 k 个元素。您以这种方式访问的块的数量是 O(log k)，因为在访问 i 个块之后，您将传递 2

i+1

- 1 个元素。这里的问题是，这假设您可以在 O(1) 时间内分配一块内存，如果是这种情况，您不妨使用前面提到的可扩展数组。 如果我想到其他什么，我一定会更新这个答案。我想知道我是否缺少一些更简单的策略？