在链表和数组中浪费了space

Question

书上有链表、数组、动态数组的比较。参数名被浪费了space.Values给出的是：

• 数组 0
• 链表O(n)
• 动态数组 O(n)

什么是浪费的space参数，为什么链表是O(n)而数组是0？

Answer 1

我想 浪费 space 是数据结构分配的 space 量减去存储其所需的 space 量元素。

数组。通常，数组除了它的元素之外什么都不包含。有时它们会存储它们的大小，或者为了内存对齐目的需要额外的内存。我会说声称数组的 'wasted space' 是 O(1) 是正确的。

链表。列表中的每个元素至少需要一个指针。因此，我们有 O(n) 'wasted space'.

动态数组。当我们在增加动态数组大小时没有足够的 space 来存储所有元素时，我们需要额外的 O(n) 内存。我们需要分配一个新的内存缓冲区，然后将元素复制到这个缓冲区。此外，通常动态数组会调整大量额外内存的大小（以分摊 O(1) add/remove 操作）。浪费内存的大小也是O(n)。

Answer 2

令 n 为动态数组中的数据量，capacity 为可用内存量。那么n <= capacity && n >= capacity/4，平均浪费量space为n*3/2 ~ O(n).