什么是“恒定的”复杂性真的吗？时间？复制/移动计数？ [英] What does "constant" complexity really mean? Time? Count of copies/moves?
问题描述
我可以想到C ++中的三个操作，可以在某种意义上描述为具有常量复杂性。我看到一些关于这意味着什么的争论（*），在我看来，我们可以说所有这些操作是恒定的，但有些比其他操作更恒定： - ） / p>
（编辑2 ：如果您已经认为自己知道答案，请先阅读这个问题的一些争论， a href =http://stackoverflow.com/questions/8627373/what-data-structure-exactly-are-deques-in-c/8628035#8628035> C ++中的哪些数据结构是deques？许多人，有相当高的分数，正在争论什么'常数'的意思。我的问题不是你可能认为的那么明显。）
> Edit ：我不需要一个底层的复杂性的意思，我想要一个明确的答案，也许与C ++标准的引用，告诉我们完全在其他线程上，有些人认为 时间与C ++标准所要求的完全无关。）
标准中的这些复杂性保证是否适用于操作的 runtime ？或者，它们只是指定所包含对象可能发生的（最大）副本/移动数量？
1。给定一个（非空）向量< int> v ，以下内容在运行时显然是不变的：
。背部（））;
（虽然脚本可能指出，这取决于数据是在缓存中还是被换出或任何！）。
2。给出列表< int& l ，执行 push_back 很简单。正确地分配一个新项目并且对链接列表中的一些指针进行洗牌。每个push_front包含一个分配，总是具有相同的内存量，因此这显然相当恒定。但是，当然，做分配的时间可能是相当可变的。内存管理可能需要花费大量的时间来找到一些合适的空闲内存。
3。但是做一个<$ c $在向量< int> 上的c> push_back 更加不可预测。大多数时候，它会很快，但每一次，它将必须重新分配空间的所有数据，并将每个元素复制到一个新的位置。所以它在运行时比单个 list :: push_front 更不可预测，但它仍然被称为常量（摊销）。 平均，向向量中添加大量数据将需要一个与添加量无关的复杂度，这就是为什么它被称为摊销常量时间。 （我是对吗？）
最后，我问了 int ，以避免使用另一种类型的复杂性。例如， vector< int> > 可能有点复杂一点，因为向量的（向量）的每个元素可能有不同的大小，例如，交换两个元素不是像case& strong> 1。。但是理想情况下，我们可以为所有向量< T> ，而不仅仅是 T = int b
$ b
复杂性总是相对于特定变量或变量集来说明。因此，当标准谈论恒定时间插入时，它谈论的是相对于列表中项目数的恒定时间。也就是说，O（1）插入意味着当前在列表中的项目数量不影响插入的总体复杂性。该列表可以有500或50000000个项目，插入操作的复杂性将是相同的。
例如， std :: list 有O（1）插入和删除;插入的复杂性不受列表中元素数量的影响。然而，内存分配器的复杂性很可能取决于已经分配的事物的数量。但是由于O（1）正在谈论列表中的项目数量，所以它没有覆盖。它不是应该的，因为那样我们将测量内存分配器的复杂性，而不是数据结构。
总之：这是一个不同的测量。 >
这意味着我们可以自由地实现我们的算法，因为我们喜欢，包括一个时间在任何实际意义上不是真正的恒定，但是我们尊重所包含对象上的操作数量。
没有相对于实现指定复杂性。它相对于算法指定。
如上所述，您可以实现
code> std :: list 与一个内存分配器相关的O（log（n））删除（其中 n 分配的数量）。然而，对于列表中的项目数量，列表中的元素的删除仍将为O（1）。 不要将复杂性与整体性能混淆。复杂性的目的是具有关于不同变量的算法的一般度量。 b 复杂性是评估算法效率的工具。复杂性不是
摊销到底是什么意思？ p>
摊销是指：
如果某物是摊销X时间，则在同一数据结构上重复该操作无限多次，X的复杂度极限。
因此， std :: vector 在后面有摊销常量时间插入。因此，如果我们获取对象并对其执行无限多次插入，则复杂度的渐近极限将与常量时间插入没有什么不同。
这意味着该操作有时可能是非恒定的，但是它将是非常数的次数将总是减少。在长期的插入，它是恒定的时间。
I can think of three operations in C++ that can be described in some sense as having 'constant' complexity. I've seen some debate(*) over what this means, and it seems to me that we could just say "all these operations are constant, but some are more constant than others" :-)
(Edit 2: If you already think you know the answer, please read some of the debate at this question before rushing in too soon: What data structure, exactly, are deques in C++? Many people, with quite high scores, are arguing over what 'constant' means. My question isn't as obvious as you might think!)
(Edit: I don't need a primer in what 'complexity' means. I want a clear answer, perhaps with quotes from the C++ standard, that tells us exactly what is supposed to be constant. Processor ticks, real-world time, or something else? On other threads, some people have argued that time is totally irrelevant to what is required by the C++ standard.)
Do these complexity guarantees in the standard apply to the runtime of the operation? Or do they simply specify the (maximum) number of copies/moves that might happen of the the contained objects? And what exactly does 'amortized' mean?
1. Given a (non-empty) vector<int> v, the following is clearly constant in runtime:
swap(v.front(), v.back());
(although a pedant might point out that it depends on whether the data is in the cache or swapped out or whatever!).
2. Given a list<int> l, doing a push_back is straightforward. Exactly one new item is allocated and a few pointers in the linked list are shuffled. Each push_front involves one allocation, always of the same amount of memory, so this is clearly fairly 'constant'. But, of course, the time to do the allocation could be quite variable. The memory-management might have to take a lot of time to find some suitable free memory.
3. But doing a push_back on a vector<int> is even more unpredictable. Most of the time, it will be very quick, but every now and then it will have to reallocate space for all the data and copy every element to a new location. So it's less predictable in terms of runtime than a single list::push_front, but it's still referred to as constant (amortized). On average, adding a lot of data to a vector will take a complexity that is independent of the amount added, and this is why it's called 'amortized constant' time. (Am I right?)
And finally, I asked about int to avoid the complexities of having another type. For example, a vector< vector<int> > might be a little more complicated to reason about because each element of the vector (of vectors) might have a different size and, for example, swapping two elements is not quite as constant as in case 1. above. But ideally, we could answer for all vector<T>, not just T=int.
(*) For an example of the debates, see the comments to these answers: What data structure, exactly, are deques in C++?
Complexity is always stated relative to a specific variable or set of variables. So when the standard talks about constant time insertion, it is talking about constant time relative to the number of items in the list. That is, O(1) insertions means that the number of items currently in the list does not affect the overall complexity of insertions. The list could have 500 or 50000000 items in it, and the complexity of the insertion operation will be the same.
For example, std::list has O(1) insertions and deletions; the complexity of insertions is not affected by the number of elements in the list. However, the memory allocator's complexity may well depend on the number of things that have already been allocated. But since the O(1) is talking about number of items in the list, it doesn't cover that. Nor is it supposed to, because then we would be measuring the complexity of the memory allocator, not the data structure.
In short: that's a different measurement.
It implies that we are free to implement our algorithm as badly as we like, including one where the time isn't really constant in any pragmatic sense, but where we have respected the number of 'operations' on the contained objects.
Complexity is not specified relative to implementations. It is specified relative to algorithms. It doesn't matter that a context could switch, because running time is not what complexity is for.
As above, you could implement std::list with a memory allocator that is O(log(n)) with respect to deletions (where n is the number of allocations). However, the deletion of an element in the list would still be O(1) with respect to the number of items in the list.
Do not confuse complexity with overall performance. The purpose of complexity is to have a general metric for algorithms with respect to different variables. The purpose of a programmer, who wants their code to run fast, is to find a reasonable implementation of an algorithm that conforms to the complexity that they need to achieve that performance.
Complexity is a tool for rating the efficiency of an algorithm. Complexity does not mean you get to stop thinking.
And what exactly does 'amortized' mean?
Amortized means this:
If something is "amortized X time", then as you repeat the operation infinitely many times on the same data structure, the complexity limits at X.
So, std::vector has "amortized constant time" insertions at the rear. So if we take the object and perform infinitely many insertions on it, the asymptotic limit of complexity will be no different than a "constant time" insertion.
In laymans terms, it means that the operation may sometimes be non-constant, but the number of times it will be non-constant will always be decreasing. Over the long run of insertions, it's constant time.
这篇关于什么是“恒定的”复杂性真的吗？时间？复制/移动计数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
