free() 的时间复杂度是多少? [英] What is the time complexity of free()?

问题描述

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

I was just wondering what the time complexity of free() is in C.

例如，让我们假设我的所有功能是:

For example let's assume all my function does is:

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

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

Is it O(n) or O(n^2)?

推荐答案

正如 Story Teller 所说，free() 的实现没有指定，这也使得它的时间复杂度未指定.

As Story Teller has stated, the implementation of free() is not specified, which makes its time complexity unspecified, too.

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

The varied concepts of administrating allocated memory can come with different complexities.

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

Just a few simplified examples of data structures used by memory managers
(note that this is NOT the data structure in the program you created):

• 对于单个 malloc()-free() 对，已分配块的链表将带有线性 O(n)，
  使你的代码 O(n^2)
• 伙伴计划将带有对数 O(log n),
  让你的代码 O(n log n)
• 强调 malloc 和 free 的时间复杂度的实现(作为快速的一个方面)，可能会接近 O(1)，我正在想象散列表
  (这可能会导致内存消耗和高 1"的损失，即常数时间可能比其他低 n 的概念更长)，
  这将使您的代码 O(n)(或 O(1) 用于低 n)

注意:
有一种方案可以在管理内存中创建内存管理器数据结构(适用于上述所有示例)，这将允许找到要释放的块并在 O(1) 中与它相关的管理数据，从而产生 O(1) 的 free().然而，提到的数据结构将通过 malloc() 进行搜索，采用提到的不同时间复杂度，用于 未使用 块(即 malloc() 的大小参数不有帮助的直接指向).假设您的代码还必须对要释放的块进行 malloc()，那么您实际上可能最终会遇到整个程序的上述复杂性.
严格来说，仅就所示的释放循环而言，任何广泛使用的内存管理器都会使您的代码 O(n)，每个 free() 的 O(1).

Note:
There is a scheme to make the memory manager data structures (applying to all examples above) within the administrated memory, that would allow finding the block to free and relative to it the administration data in O(1), resulting in a free() of O(1). The mentioned data structures, will however be searched by malloc() taking the mentioned different time complexities for an unused block (i.e. one which the size parameter to malloc() does not helpfully point to directly). Assuming that your code also has to malloc() the blocks you are freeing, you will probably actually end up with the mentioned complexities for the whole program.
Strictly speaking, with respect to only the shown freeing loop, any widely used memory manager will make your code O(n), with O(1) for each free().

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

这篇关于free() 的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！