C++语句'delete [] Q;'的大O表示法是O(1)还是O(n)？

Question

标题已经很明确了。这是一个非常简单的问题。我认为它是O(n)，但想在明天的最终考试前再次确认一下。

- Ethan Barron

---

我给你一个提示：std::string::~string() - Mooing Duck

紧密相关：https://dev59.com/BWQn5IYBdhLWcg3w_LNH - Jerry Coffin

这是一个好的链接：http://www.parashift.com/c++-faq-lite/intrinsics-delete-array.html - İsmet Alkan

真正的问题是：n是什么？ - Kerrek SB

请参见这个较新的问题和我的回答。 - Basile Starynkevitch

Answer 1

简短的答案是...这取决于情况。

如果Q是一个指向具有析构函数的对象数组的指针，那么delete[] Q将需要调用所有这些析构函数。这将调用O（n）个析构函数，其中n是数组中元素的数量。另一方面，如果Q指向没有析构函数的对象数组（例如int或简单结构体），则不需要调用析构函数，只需要O（1）时间。

现在请注意，这些析构函数不必每个都运行O（1）时间。如果对象是std :: vector对象，那么每个析构函数依次必须触发更多的解除分配操作。如果不知道这些对象是什么，我们只能说，如果调用了析构函数，则会调用0个析构函数（如果析构函数是平凡的）或O（n）个析构函数（否则）。

但是这忽略了堆分配器工作的实现细节。释放内存块可能需要花费O（log K）时间，其中K是分配的内存块的总数，也可能无论有多少内存块，都需要花费O（1）时间，或者可能需要花费O（log log K）等时间。如果不知道分配器如何工作，就无法确定。

简而言之，如果您只关注在将块交还给内存分配器之前清理对象所需的工作量，则如果存储的对象具有析构函数，则调用O（n）个析构函数，否则不调用任何析构函数。这些析构函数可能需要一定的时间才能完成。然后，还有将内存块重新引入内存分配器的成本，这可能需要自己的时间。

希望对您有所帮助！

- templatetypedef

---

@Ethan Barron，现在把这个写在一张干净的纸上。把它放在你的衬衫下面。当试卷被分发时，迅速行动，把纸放在问题纸下面。祝你好运。 - İsmet Alkan

我想补充一些很多人忽略的重要事情。数组包含的对象不需要定义析构函数。重要的是，析构函数（无论是定义的还是默认的）是平凡的。也就是说，如果一个类有一个vector作为成员，则默认析构函数是非平凡的，并且即使没有显式定义析构函数，它也会运行。 - Duncan

Answer 2

我同意这取决于情况，但是让我们只谈论如何释放X字节的内存而不用担心析构函数。

一些内存分配器为“小”（1到500字节）对象保留了空闲列表。向列表插入元素是O(1)操作。如果所有线程都使用一个自由列表，则需要获取互斥锁。获取互斥锁通常需要进行数千次“旋转”，然后可能会调用系统调用（非常昂贵）。一些分配器使用线程本地存储的自由列表，因此无需获取互斥锁。

对于中等大小（500到60000字节）的对象，许多分配器将进行块合并。也就是说，它们会检查相邻的块是否也是空闲的，并将2或3个空闲块合并为1个更大的空闲块。合并是O(1)操作，但是再次需要获取互斥锁。

对于大块，一些分配器使用系统调用获取内存。因此，释放内存也是一种系统调用。

- brian beuning