内存分配的时间复杂度

Question

使用new、malloc等动态内存分配的时间复杂度是多少？我对内存分配器的实现方式知之甚少，但我认为答案是它取决于实现。因此，请回答一些更常见的案例/实现。

编辑：我依稀记得听说堆分配在最坏的情况下是无界的，但我对平均/典型情况真的很感兴趣。

Answer 1

在处理O表示法时，您必须意识到的一件事是，理解 n 是什么通常非常重要。如果 n 与你可以控制的东西相关（例如：你想要排序的列表中的元素数量），那么仔细观察它是有意义的。

在大多数堆实现中， n 是管理器正在处理的连续内存块的数量。这绝对是不通常由客户控制的东西。客户端真正控制的唯一 n 是她想要的内存块的大小。通常这与分配器所花费的时间无关。大型 n 可以像小型 n 一样快速分配，或者可能需要更长时间，或者甚至可能无法使用。所有这些都可以针对相同的 n 进行更改，具体取决于之前的其他客户端的分配和解除分配方式。实际上，除非您正在实现堆，否则正确的答案是它是非-deterministic

这就是硬实时程序员试图避免动态分配（启动后）的原因。

Answer 2

堆分配器的时间复杂度在不同系统上可能会有所不同，具体取决于它们可能优化的内容。

在桌面系统上，堆分配器可能使用不同策略的混合，包括缓存最近的分配，常见分配大小的后备列表，具有特定大小特征的内存块的容器等，以尝试保持分配时间，但也保持碎片可管理。有关使用的各种技术的概述，请参阅Doug Lea的malloc实现说明： http： //g.oswego.edu/dl/html/malloc.html

对于更简单的系统，可以使用第一拟合或最佳拟合的策略，其中空闲块存储在链表上（其将给出O（N）时间，其中N是空闲块的数量）。但是可以使用更复杂的存储系统（例如AVL树）来在O（log N）时间内找到空闲块（ http://www.oocities.org/wkaras/heapmm/heapmm.html 。

实时系统可能使用堆分配器，如TLSF（Two-Level Segregate Fit），其分配成本为O（1）： http://www.gii.upv.es/tlsf/

Answer 3

我认为它通常是O（n），其中n是可用内存块的数量（因为你必须扫描可用的内存块以找到合适的内存块）。

话虽如此，我已经看到了可以使其更快的优化，特别是根据它们的大小范围维护多个可用块列表（因此，在一个列表中小于1k的块，在1k到10k的块在另一个列表中等等。）

然而，这仍然是O（n），只是使用较小的n。

我有兴趣看到你的消息来源有一个无限的堆分配（如果，那么，你的意思是它可能需要永远）。

Answer 4

查看典型分配器的工作原理。

指针碰撞分配器在 O（1）中工作，并且它是一个小的“ 1 ”。

对于隔离存储分配器，k字节的分配意味着“从列表中返回第一个块（ n ）”。其中List（ n ）是n个字节的块列表，其中 n＆gt; = k 。它可能发现List（ n ）为空，因此下一个列表中的块（List（ 2n ））必须是将所有 n 字节的块放到List（ n ）上进行拆分，此效果可能会波动所有可用的大小，从而形成一个 O（ns）的复杂性，其中ns是可用的不同大小的数量， ns = log（N）其中 N 的大小为最大的块大小可用，所以即使这样也会很小。在大多数情况下，特别是在分配和释放了大量块后，复杂性为 O（1）。

Answer 5

仅两点说明：

• TLSF 是 O(1)，因为它没有单个循环；并可管理高达 2Gb。虽然真的很难相信，但只要检查一下代码就知道了。

• “最合适”的策略（找到紧块）最适合 实现小碎片化。证明这一说法绝非易事，事实上它还没有得到正式证明，但有很多证据表明这一点。（很好的研究课题）。