c - free() 的时间复杂度是多少？

Question

我只是想知道 free() 在 C 中的时间复杂度是多少。

例如，假设我的函数所做的是:

for (int i = 0; i < n; i++) {
    free(ptr[i]); // this is just an example to show n pointers
}

是 O(n) 还是 O(n^2)？

Answer 1

正如 Story Teller 所说，未指定 free() 的实现，因此其时间复杂度也未指定。

管理分配内存的不同概念可能具有不同的复杂性。

只是内存管理器使用的数据结构的几个简化示例
(请注意，这不是您创建的程序中的数据结构):

• 对于单个 malloc()-free() 对，分配 block 的链表将带有线性 O(n)，
  使你的代码复杂度为 O(n^2)
• 伙伴方案会带有对数 O(log n)，
  使你的代码 O(n log n)
• 强调 malloc 和 free 的时间复杂度的实现(作为快速的一个方面)，可能会接近 O(1)，我在想象哈希表
  (这可能会带来内存消耗的惩罚和“高 1”，即常数时间可能比其他具有低 n 的概念更长)，
  这将使您的代码复杂度为 O(n)(或低 n 时复杂度为 O(1))

注意:
有一种方案可以在受管理的内存中创建内存管理器数据结构(适用于上述所有示例)，这将允许找到要释放的 block 以及与其相关的 O(1) 中的管理数据，从而产生 O(1) 的免费()。然而，上述数据结构将由 malloc() 以上述不同的时间复杂度搜索 unused block (即 malloc() 的 size 参数不有帮助的直接点)。假设您的代码还必须 malloc() 您正在释放的 block ，您实际上可能会遇到整个程序所提到的复杂性。
严格来说，仅就所示的释放循环而言，任何广泛使用的内存管理器都会使您的代码复杂度为 O(n)，每个 free() 的复杂度为 O(1)。

(感谢 Stargateur 迫使我更具体地思考这个问题所涉及的确切情况。)