c++ - "constant"复杂度的真正含义是什么？时间？复制/移动的数量？

Question

就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持，但这个问题可能会引起辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the help center为指导。




9年前关闭。




我可以想到 C++ 中的三个操作，它们在某种意义上可以被描述为具有“恒定”的复杂性。我已经看到一些关于这意味着什么的争论(*)，在我看来，我们可以说“所有这些操作都是恒定的，但有些比其他操作更恒定”:-)

( 编辑 2 : 如果您已经认为自己知道答案，请在过早进入之前阅读此问题的一些辩论:What data structure, exactly, are deques in C++? 很多得分很高的人正在争论什么'常数'的意思。我的问题并不像你想象的那么明显!)

( 编辑 :我不需要了解“复杂性”的含义。我想要一个明确的答案，也许是来自 C++ 标准的引号，它告诉我们什么应该是恒定的。处理器滴答声，真实世界的时间，还是其他什么？在其他线程上，有些人认为时间与 C++ 标准的要求完全无关。)

标准中的这些复杂性保证是否适用于操作的运行时？或者他们是否只是指定了所包含对象可能发生的(最大)复制/移动次数？ “摊销”究竟是什么意思？

1. 给定一个(非空)vector<int> v ，以下在运行时显然是恒定的:

swap(v.front(), v.back());

(尽管学究可能会指出这取决于数据是在缓存中还是换出或其他什么!)。

2. 给定一个 list<int> l ，做一个 push_back很简单。恰好分配了一个新项目，并打乱了链表中的一些指针。每个 push_front 都涉及一个分配，总是具有相同的内存量，因此这显然是相当“恒定”的。但是，当然，进行分配的时间可能会有很大差异。内存管理可能需要花费大量时间才能找到一些合适的空闲内存。

3. 但是做一个 push_back在 vector<int>更是难以预料。大多数情况下，它会非常快，但它必须时不时地为所有数据重新分配空间并将每个元素复制到新位置。因此，它在运行时的可预测性不如单个 list::push_front ，但它仍然被称为常数(摊销)。平均而言，向一个 vector 添加大量数据将需要一个与添加量无关的复杂性，这就是为什么它被称为“摊销常数”时间。 (我对吗？)

最后，我问了 int以避免具有另一种类型的复杂性。例如， vector< vector<int> >推理可能有点复杂，因为( vector 的) vector 的每个元素可能具有不同的大小，例如，交换两个元素并不像 那样恒定。 1. 以上。但理想情况下，我们可以回答所有 vector<T> ，不仅仅是 T=int .

(*) 有关辩论的示例，请参阅对这些答案的评论: What data structure, exactly, are deques in C++?

Answer 1

复杂性总是相对于特定变量或变量集来表述的。因此，当标准谈论恒定时间插入时，它谈论的是相对于列表中项目数量的恒定时间。也就是说，O(1) 次插入意味着当前列表中的项数不影响插入的整体复杂度。列表中可能有 500 或 50000000 个项目，插入操作的复杂度将相同。

例如，std::list有 O(1) 次插入和删除；插入的复杂性不受列表中元素数量的影响。然而，内存分配器的复杂性很可能取决于已经分配的东西的数量。但是由于 O(1) 是在谈论列表中的项目数，因此它不包括在内。也不应该，因为那样我们将测量内存分配器的复杂性，而不是数据结构。

简而言之:这是一个不同的衡量标准。

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.

未指定相对于实现的复杂性。它是相对于算法指定的。上下文可以切换并不重要，因为运行时间不是复杂性的原因。

如上，你可以实现 std::list使用一个内存分配器，对于删除操作是 O(log(n))(其中 n 是分配的数量)。但是，相对于列表中的项目数，删除列表中的元素仍然是 O(1)。

不要将复杂性与整体性能混淆。复杂性的目的是针对不同变量的算法有一个通用度量。希望他们的代码快速运行的程序员的目的是找到一个算法的合理实现，该算法符合他们实现该性能所需的复杂性。

复杂性是评估算法效率的工具。复杂性并不意味着您可以停止思考。

And what exactly does 'amortized' mean?

Amortized这意味着:

如果某事是“摊销 X 时间”，那么当您在同一数据结构上无限次重复操作时，X 处的复杂性限制。

所以， std::vector在后面插入了“摊销固定时间”。因此，如果我们取对象并对其执行无限次插入，则复杂性的渐近极限将与“恒定时间”插入没有什么不同。

通俗地说，就是操作有时可能是非常数的，但是非常数的次数会一直递减。在长期的插入过程中，时间是恒定的。