Time complexity and insertion into std::list
Insertion on std::list is claimed to be constant time, regardless whether it is made in the front, middle or back of the container.
On the other hand, acquisition of memory for the new inserted item is handled by the standard allocator, which uses operator new. AFAIK operator new is not guaranteed to have constant time.
When operator new looks for available space in the heap, it must be sure that it will not override previously allocated memory, therefore it has to keep track of what has already been allocated on the heap. I conclude that insertion must be at least linear on the number of elements already in the list.
What is wrong with this reasoning?
My question reads:
Note: It is important to note the difference between "real life time" and the "time" talked about when diving into time complexity. When time complexity is the topic it's important that one doesn't confuse the usage of "time" with "milliseconds spent doing something".
WHAT IS THE DEFINITION OF constant time?
Wikipedia is often said to be a bad reference in many contexts, but in this case (and a lot of others) the definitions available is correct and will help to describe how things work.
The article about time complexity says the following about constant time:
Wikipedia - Constant Time
An algorithm is said to be constant time (also written as O(1) time) if the value of T(n) is bounded by a value that does not depend on the size of the input. For example, accessing any single element in an array takes constant time as only one operation has to be performed to locate it.
Since the insertion into a std::list does not depend on the number of elements in the list we say that insertion is constant time; each insertion, no matter where or when, consists of the same number of elementary operations; none related to the size of the list.
But what if operator new is not O(1) ?
Honestly it doesn't matter, even if the complexity of new would implicitly depend on how many previous entities we have allocated, the complexity of our list-insertion will be unchanged. The allocation is indifferent to the size of the list.
O(1) , constant time, means that the time to execute something is unrelated to the size of input in any given algorithm. Even if new isn't O(1) , our insertation is O(1) since it only describes itself.
The paths taken inside our list inseration all includes operator new . The path doesn't change because of the size of our list, the path's complexity is constant time.
So what are we dealing with?
Hannibal_Smith in ##c++ at freenode said something clever, and I liked it so much that I will include it in this post: The cost model is a pointer machine.
Even though the sentence might be a little bit misleading it does serve the purpose of explaining how the insertion is O(1) even though parts of the algorithm isn't constant time.
The insertion into a std::list is described from the perspective of being a machine who only deals with pointers, and from this perspective one cannot say that it is nothing other than O(1) . The allocation done inside this algorithm is not related to the complexity of the algorithm itself.
This is a very tricky question that has been discussed at some length in this thread.
If I could try to summarize it: The standard makes some subtle distinctions. If you read it precisely, some operations are indeed specified to be "constant time", but std::list insertion is not among them. It is specified to be "constant" ( Edit : wrong, see below) and the "General Container Requirements" clause (23.2.1 in this draft of the C++ standard) explains that
All of the complexity requirements in this Clause are stated solely in terms of the number of operations on the contained objects.
( Edit : as Filip Roséen pointed out, I was mistaken; std::list insertion is specified to be "constant time", but I believe the General Requirements clause still governs). So because list insertion only has to work on a single object and its neighbors, it's "constant complexity" even though it may not necessarily be "constant time complexity" because there are no time complexity guarantees for the allocation.
Pragmatically, a decent memory allocator will not be linear in the number of objects allocated, though it probably is not constant time either.
链接地址: http://www.djcxy.com/p/78272.html上一篇: Lambda捕获参数引起歧义
下一篇: 时间复杂度和插入到std :: list