Is Big-O of the C++ statement 'delete [] Q;

问题:

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

回答1:

The short answer is... it depends.

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.

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.

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.

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.

Hope this helps!

回答2:

I agree with it depends, but lets just talk about freeing X bytes of memory and not worry about destructors.

Some memory allocators keep free lists for "small" (1 to 500 byte) objects. An insert to a list is O(1). If there is one free list for all threads, then it needs to acquire a mutex. Acquiring a mutex usually involves up to a couple 1000 "spins" and then maybe a system call (which is very expensive). Some allocators have free lists per thread using thread local storage, so then their is no mutex acquire.

For a medium (500 to 60000 bytes) sized object many allocators will do block coalescing. That is they check if the adjoining blocks are also free, and they merge the 2 or 3 free blocks to make 1 bigger free block. Coalescing is O(1), but again it needs to acquire a mutex.

For large blocks some allocators get the memory using a system call. So freeing the memory is also a system call.