标题是不言自明的。 很简单的问题。 我认为这是为O（n），但我想明天决赛前进行验证。
Answer 1:
简短的答案是...它依赖。
如果Q是一个指针，它指向具有析对象的数组，然后delete[] Q需要调用所有这些析构函数。 这将调用O（n）的析构函数，其中n是阵列中的元素的数量。 在另一方面，如果Q指向不具有析构函数（例如，对象的数组int S或简单struct或多个），那么没有析构函数需要被调用，这只需O（1）时间。
现在请注意，这些析构函数不必在O（1）每次运行。 如果对象，比方说， std::vector对象，然后依次对每个析构函数不得不火了更多的释放操作。 不知道更多关于这些对象，我们只能说的是，如果有析构函数调用，将有0析构函数称为如果析构函数是微乎其微的，O（n）的析构函数，否则调用。
但是，这忽略了堆分配是如何工作的实现细节。 这有可能是重新分配的内存块可能需要为O（log K）时间，其中K是分配的总块数，或者它可能需要O（1）时间，无论怎样的内存多块有，也可能需要O（log日志K），等等。如果不知道如何分配器的作品，你真的不能确定。
总之，如果你仅关注递块回内存分配器之前清理对象所需的工作，也有所谓的O（n）的析构函数，如果存储的对象有析构函数和析构函数0，否则叫。 这些析构函数可能需要很长时间才能完成一个平凡的量。 然后，是重新采用的内存模块放回内存分配器的成本，这可能需要它自己的时间。
希望这可以帮助！
Answer 2:
我同意这取决于，还是让我们只是谈论释放的内存X字节，而不必担心析构函数。
有些内存分配器保持为“小”（1至500个字节）的对象空闲列表。 到一个列表中的插入是O（1）。 如果所有线程一个空闲列表，那么它需要获取互斥锁。 获取互斥通常包括了一对夫妇1000“旋转”，然后也许一个系统调用（这是非常昂贵）。 有些allocator有使用线程本地存储每个线程的空闲列表，所以后来他们没有互斥锁获取。
对于介质（500到60000个字节）大小的对象许多分配器将做块的聚结。 这是他们检查，如果相邻块也是免费的，而且它们合并2个或3个免费块，使1个大空闲块。 聚结是O（1），但同样需要获得一个互斥体。
对于大一些的块分配器获得使用系统调用的内存。 因此，释放内存也是一个系统调用。
文章来源: Is Big-O of the C++ statement 'delete [] Q;' O(1) or O(n)?
