标题是不言自明的。很简单的问题。我认为这是 O(n) 但想在明天的决赛之前进行验证。
问问题
2002 次
2 回答
18
简短的回答是……这取决于。
如果Q是指向具有析构函数的对象数组的指针，则delete[] Q需要调用所有这些析构函数。这将调用 O(n) 析构函数，其中 n 是数组中元素的数量。另一方面，如果Q指向一个没有析构函数的对象数组（例如ints 或 simple structs），则不需要调用析构函数，这只需 O(1) 时间。
现在请注意，这些析构函数不必每次都在 O(1) 时间内运行。如果对象是std::vector对象，那么每个析构函数又必须触发更多的释放。在不了解这些对象是什么的情况下，我们只能说，如果调用了析构函数，那么如果析构函数是微不足道的，则将调用 0 个析构函数，否则将调用 O(n) 个析构函数。
但这忽略了堆分配器如何工作的实现细节。释放一块内存可能需要 O(log K) 时间，其中 K 是已分配块的总数，或者无论有多少内存块，都可能需要 O(1) 时间，或者可能需要O(log log K) 等。如果不知道分配器是如何工作的，你真的无法确定。
简而言之，如果您只关注在将块交给内存分配器之前清理对象所需的工作，那么如果存储的对象具有析构函数，则调用 O(n) 析构函数，否则调用 0 个析构函数。这些析构函数可能需要很长时间才能完成。然后，将内存块重新引入内存分配器会产生成本，这可能需要花费自己的时间。
希望这可以帮助！
于 2013-05-09T21:59:34.627 回答
3
我同意这取决于，但让我们谈谈释放 X 字节的内存而不用担心析构函数。
一些内存分配器为“小”（1 到 500 字节）对象保留空闲列表。插入列表是 O(1)。如果所有线程都有一个空闲列表，那么它需要获取一个互斥锁。获取互斥锁通常涉及多达 1000 次“旋转”，然后可能是系统调用（这非常昂贵）。一些分配器使用线程本地存储为每个线程提供空闲列表，因此它们不是互斥锁获取。
对于中等（500 到 60000 字节）大小的对象，许多分配器会进行块合并。也就是说，他们检查相邻的块是否也是空闲的，然后将 2 或 3 个空闲块合并为 1 个更大的空闲块。合并是 O(1)，但它再次需要获取互斥锁。
对于大块，一些分配器使用系统调用来获取内存。所以释放内存也是一个系统调用。
于 2013-05-09T22:12:59.997 回答