时间复杂度和插入std :: list

Question

无论是在容器的前面,中间还是后面,都声称std :: list上的插入是恒定时间.

另一方面,为新插入项目获取内存由标准分配器处理,该分配器使用operator new.AFAIK operator new不保证有恒定的时间.

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

这个推理出了什么问题？

---

我的问题是:

• 当获取每个新节点的内存不能保证是恒定时间时,怎么可能说列表上的插入是恒定时间？

Answer 1

^{注意：在深入研究时间复杂性时，请务必注意“现实生活时间”和所讨论的“时间”之间的区别。当时间复杂度成为主题时，重要的是不要将“时间”的用法与“做某事所花费的毫秒数”混淆。}

恒定时间的定义是什么？

在许多情况下，维基百科通常被认为是一个糟糕的参考，但在这种情况下（以及许多其他情况下），可用的定义是正确的，并且将有助于描述事物的工作原理。

关于时间复杂度的文章对常数时间做了以下说明：

维基百科 - 恒定时间

如果 T(n) 的值受不依赖于输入大小的值限制，则该算法被称为恒定时间（也写为 O(1) 时间）。例如，访问数组中的任何单个元素都需要恒定的时间，因为只需执行一次操作即可找到它。

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

但如果operator new不是呢O(1)？

老实说，这并不重要，即使 的复杂性隐式new取决于我们之前分配的实体数量，列表插入的复杂性也将保持不变。分配与列表的大小无关。

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

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

那么我们在处理什么呢？

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

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

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