是C ++语句的大O“删除[]问;' O（1）或O（N）？ [英] Is Big-O of the C++ statement 'delete [] Q;' O(1) or O(n)?

问题描述

标题是不言自明。很简单的问题。我认为这是为O（n），但我想明天的决赛之前进行验证。

Title is self-explanatory. Very easy question. I think it's O(n) but wanted to verify before my final tomorrow.

推荐答案

简短的答案是...它依赖。

The short answer is... it depends.

如果问：是一个指向析构函数对象的数组，那么删除[]问将需要调用所有的析构函数。这将调用O（n）的析构函数，其中n是数组中元素的个数。在另一方面，如果问：指向没有析构函数对象的数组（例如， INT s或简单的结构 S），那么没有析构函数需要被调用，而只需要O（1）时间。

If Q is a pointer to an array of objects that have destructors, then delete[] Q will need to call all of those destructors. This will call O(n) destructors, where n is the number of elements in the array. On the other hand, if Q points to an array of objects that don't have destructors (for example, ints or simple structs), then no destructors need to be called, which takes only O(1) time.

现在注意那些析不必在O（1）每次运行。如果对象，比方说，的std ::矢量对象，然后依次在每个析构函数不得不火了更多的释放操作。不知道更多关于这些对象，我们能够说的是，如果有析构函数调用，将有0析构函数称为如果析构函数是微乎其微的，O（n）的析构函数否则所谓。

Now note that those destructors don't have to run in O(1) time each. If the objects are, say, std::vector objects, then each destructor in turn has to fire off more deallocations. Without knowing more about what those objects are, all we can say is that if there are destructors called, there will be 0 destructors called if the destructors are trivial and O(n) destructors called otherwise.

但是，这忽略了堆分配是如何工作的实施细节。这有可能是重新分配的内存块可能需要为O（log K）时间，其中K是分配的总块数，或者它可能需要O（1）时间，无论怎样的记忆很多块有，也可能需要O（日志记录K），等等。如果不知道分配器是如何工作的，你真的不能确定。

But this ignores the implementation detail of how the heap allocator works. It's possible that deallocating a block of memory might take O(log K) time, where K is the total number of allocated blocks, or it might take O(1) time regardless of how many blocks of memory there are, or it might take O(log log K), etc. Without knowing how the allocator works, you honestly can't be sure.

总之，如果你仅关注递块回内存分配器之前清理对象所需的工作，也有所谓的O（n）的析构函数如果存储的对象有析构函数和析构函数0，否则叫。这些析构函数可能需要很长时间才能完成一个平凡的金额。然后，有重新引入的内存块返回到存储器分配器，这可能需要其自己的时间量的成本。

In short, if you focus purely on the work required to clean up the objects before handing the block back to the memory allocator, there are O(n) destructors called if the objects stored have destructors and 0 destructors called otherwise. These destructors might take a nontrivial amount of time to complete. Then, there's the cost of reintroducing the block of memory back into the memory allocator, which might take its own amount of time.

希望这有助于！

这篇关于是C ++语句的大O“删除[]问;' O（1）或O（N）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！