algorithm - 缓存无关堆栈和队列的复杂性

Question

我读到可以使用加倍数组来实现缓存不经意堆栈。

有人可以解释分析如何使每次推送和弹出都具有 1/B 摊销 I/O 复杂度吗？

Answer 1

栈支持以下操作:

• 推送
• 流行

虽然这两个操作可以使用具有 O(1) push 和 O(1) pop 的单链表来执行，但它会遇到缓存问题，因为存储的元素分散在内存中。对于这种方法，我们推到列表的前面，然后从列表的前面弹出。

我们可以使用 dynamic array作为我们的数据结构，插入和弹出到数组的末尾。 (我们将跟踪数组中最后填充的位置作为我们的索引，并在我们压入和弹出元素时修改它)。

弹出的时间复杂度为 O(1)，因为我们不需要调整数组的大小。

如果数组末尾有多余的空间，则插入O(1)。

问题是当我们试图压入一个元素但没有空间容纳它时。在本例中，我们创建了一个两倍大 (2n) 的新数组，然后将 n 个元素中的每一个复制过来，然后压入该元素。

假设我们有一个大小为 n 的数组，但开始时为空。

如果我将 n+1 个元素压入数组，那么前 n 个元素需要 O(1)*n = O(n) 的时间。

+1 元素需要 O(n) 时间，因为它必须构建数组的新副本。

所以将 n+1 个元素插入数组是 O(2n)，但我们可以去掉常量，只说它是 O(n) 或元素数量的线性。

因此，虽然推送单个元素可能比持续操作花费更长的时间，但推送大量元素需要线性工作量。

动态数组是缓存友好的，因为所有元素都尽可能靠近，所以多个元素应该在相同的缓存行中。