使用new、malloc等动态内存分配的时间复杂度是多少？我对内存分配器的实现方式知之甚少，但我认为答案是它取决于实现。因此，请回答一些更常见的案例/实现。
编辑: 我依稀记得听说堆分配在最坏的情况下是无界的，但我对平均/典型情况真的很感兴趣。
最佳答案
在处理 O 表示法时，您必须意识到的一件事是，理解 n 是什么通常非常重要。如果n与你可以控制的东西相关(例如:你想要排序的列表中的元素数量)，那么仔细研究它是有意义的。
在大多数堆实现中，n 是管理器正在处理的连续内存块的数量。这绝对不是通常由客户控制的事情。客户端真正可以控制的唯一n是她想要的内存块的大小。通常这与分配器花费的时间无关。大的 n 可以像小的 n 一样快速分配，或者可能需要更长的时间，或者甚至可能无法提供服务。对于相同的n，所有这些都可能会发生变化，具体取决于其他客户端之前的分配和释放方式。所以实际上，除非您正在实现堆，否则正确的答案是它不是-确定性。
这就是为什么硬实时程序员试图避免动态分配(启动后)。
关于optimization - 内存分配的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/282926/