内存分配的时间复杂度
使用new，malloc等dynamic内存分配的时间复杂度是多less？ 我对于如何实现内存分配器知之甚less，但我认为答案在于实现。 因此，请回答一些更常见的情况/实施。
编辑：我依稀记得在最坏的情况下堆分配是无限的，但我真正感兴趣的平均/典型的情况。
在处理O符号时，你必须意识到的一件事情是，理解n是非常重要的。 如果n是与你可以控制的东西相关的东西（例如：你想要sorting的列表中的元素的数量），那么看看它是有意义的。
在大多数堆实现中， n是pipe理器正在处理的连续内存块的数量。 这决不是典型的客户端控制。 客户真正控制的唯一的事情就是她想要的大块内存。 通常这与分配器所花费的时间无关。 大n可以像小n一样快速分配，否则可能需要更长的时间，否则甚至可能是不可预见的。 所有这一切都可以改变为相同的n取决于以前的分配和从其他客户端释放进来。所以真的，除非你正在实施堆，那么正确的答案是，它是非确定性的 。
这就是为什么硬实时程序员试图避免dynamic分配（启动后）。
堆分配器的时间复杂度可能在不同的系统上有所不同，具体取决于它们可能优化的内容。
在桌面系统上，堆分配器可能会混合使用不同的策略，包括caching最近分配，公用分配大小的后备列表，具有一定大小特征的内存块的bin等等，以便保持分配时间不变，同时保持碎片可pipe理性。 请参阅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（两级分离适配）这样的堆分配器，它具有O（1）分配成本： http : //www.gii.upv.es/tlsf/
我认为它通常是O（n），其中n是可用内存块的数量（因为您必须扫描可用的内存块以find合适的内存块）。
话虽如此，我已经看到优化，可以使其更快，特别是根据其大小范围维护多个可用块的列表（所以小于1k的块在一个列表中，1k到10k的块在另一个列表中等等）。
这仍然是O（N），但是，只有一个更小的N。
我有兴趣看到你的源码有一个堆分配是无限的（如果这样，你的意思是它可能会永远）。
只要看看典型的分配器是如何工作的。
一个凹凸指针分配器在O（1）中工作 ，并且它是一个小的“ 1 ”。
对于分隔存储分配器，分配k字节意味着“从List（ n ）返回第一个块”，其中List（ n ）是其中n> = k的n个字节的块的列表。 它可能会发现List（ n ）是空的，所以来自下一个列表（List（ 2n ））的块将不得不被拆分，并且将两个结果的n个字节块放到List（ n ）上，这个效应可能会波及通过所有可用的大小，使得复杂度为O（ns） ，其中ns是可用的不同大小的数目，并且ns = log（N）其中N是最大块大小的大小，所以即使是小的。 在大多数情况下，特别是在一些块被分配和释放之后，复杂性是O（1） 。
只有两句话：
-
TLSF在O（1）中是没有单一循环的; 并pipe理高达2Gb。 虽然真的很难相信，只是检查代码。
-
“最适合”政策（find紧密的区块）是最适合实现小碎片化的。 certificate这一说法远非微不足道，事实上它还没有得到正式的证实，但有很多证据表明这一点。 （很好的研究课题）。
