链表和数组中浪费的空间

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

大堆 . 通常,数组除了元素之外什么都不包含。有时,它们会存储其大小,或者出于内存对齐的目的需要额外的内存。我想说,声称阵列的“浪费空间”是正确的 O(1) .

链接列表 . 对于列表的每个元素,我们至少需要一个指针。因此,我们有 O(n) “浪费的空间”。

动态数组 . 我们需要一个额外的 O(n) 当我们在增大动态数组的大小时,并没有足够的空间来存储所有元素时的内存。我们需要分配一个新的内存缓冲区,然后将元素复制到此缓冲区。此外,通常动态数组会通过大量额外内存调整大小(以摊销 O(1) 添加/删除操作)。浪费的内存大小为 O(n) 也

设n为动态数组中的数据量,capacity为可用内存量。然后n<=容量(&A)&n>=容量/4,平均浪费空间量为n*3/2~O(n)。