内存分配的时间复杂度

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

编辑:我依稀记得在最坏的情况下听到堆分配是无限的,但我真的对平均/典型情况感兴趣.

1> T.E.D...：

---

在处理O符号时你必须意识到的一件事是,理解n是什么通常非常重要.如果n是与你可以控制的东西相关的东西(例如:你想要排序的列表中的元素数量),那么仔细观察它是有意义的.

在大多数堆实现中,n是管理器正在处理的连续内存块的数量.这绝对不是通常在客户控制下的东西.唯一的ñ客户真正拥有控制权是记忆,她希望块的大小.通常这与分配器所花费的时间无关.大n可以像小n一样快速分配,或者可能需要更长时间,或者甚至可能是不可预测的.所有这些都可以改变相同的n,这取决于之前的分配和来自其他客户端的解除分配的方式.实际上,除非您正在实现堆,否则正确的答案是它是非确定性的.

这就是硬实时程序员试图避免动态分配(启动后)的原因.

---

你的意思是"正确的答案是它没有明确定义"."非确定性"意味着不同的东西.见http://en.wikipedia.org/wiki/Nondeterministic_algorithm

---

@Daniel - 我正在使用这个术语,因为它在实时编程圈中很常用.例如,我的RTOS文档包含一个"非确定性C RTL调用"表,并且"确定性内存"上有一整页(与Window的非确定性内存相对).作为CS中MS的自豪持有者,我知道你来自哪里,对不起.

2> Michael Burr..：

---

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

在桌面系统上,堆分配器可能使用不同策略的混合,包括缓存最近的分配,常见分配大小的后备列表,具有特定大小特征的内存块的容器等,以尝试保持分配时间,但也可以保持碎片可管理.有关使用的各种技术的概述,请参阅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/