c++ - 时间复杂度和插入 std::list

Question

在 std::list 上的插入声称是常数时间，不管它是否在容器的前部、中部或后部制作。

另一方面，新插入项的内存获取由标准分配器，它使用 operator new。不能保证 AFAIK operator new有固定的时间。

当 operator new 在堆中查找可用空间时，必须确保它不会覆盖以前分配的内存，因此它必须保持跟踪已经在堆上分配的内容。我的结论是插入必须至少与列表中已有元素的数量成线性关系。

这个推理有什么问题？

---

我的问题是:

• 怎么可能说列表中的插入是不变的时间，当为每个新节点获取内存时不保证是常数时间？

Answer 1

^{注意: 重要的是要注意“真实生活时间”与深入研究时间复杂度时所谈论的“时间”之间的区别。当时间复杂度成为主题时，重要的是不要将“时间” 与“做某事花费的毫秒数” 混淆。}

---

恒定时间的定义是什么？

维基百科在许多情况下常被认为是不好的引用资料，但在这种情况下(以及许多其他情况下)可用的定义是正确的，并且有助于描述事物的运作方式。

关于time complexity的文章以下是关于恒定时间的内容:

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.

---

因为插入 std::list 不依赖于列表中元素的数量，所以我们说插入是常数时间；每次插入，无论何时何地，都包含相同数量的基本操作；与列表的大小无关。

---

---

但是如果 operator new 不是 O(1) 怎么办？

老实说，这并不重要，即使 new 的复杂性隐含地取决于我们分配了多少以前的实体，我们的 list-insertion 的复杂性也会保持不变。分配与列表的大小无关。

O(1)，常数时间，意味着在任何给定算法中执行某事的时间与输入大小无关。即使 new 不是 O(1)，我们的插入也是 O(1)，因为它只描述它自己。

在我们的列表插入中采用的路径都包括operator new。路径不会因为列表的大小而改变，路径的复杂度是常数时间。

---

---

那么我们在处理什么？

Hannibal_Smith 在 ##c++ at freenode 中说了一些聪明的话，我非常喜欢它，所以我将把它包括在这篇文章中:成本模型是指针机。

尽管这句话可能有点误导，但它确实用于解释插入是如何O(1) 的，即使部分算法不是恒定时间.

std::list的插入是从一个只处理指针的机器的角度来描述的，从这个角度不能说它不是别的O (1)。该算法内部完成的分配与算法本身的复杂性无关。