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

2018-06-28 00:22:24

无论是在容器的前部，中部还是后部制作，std :: list上的插入声称是恒定时间。

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

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

这个推理有什么问题？

我的问题是：

如何说列表中的插入是恒定的时间，当为每个新节点获取内存不保证是恒定的时间？

注意：当考虑时间复杂性时，注意“真实生活时间”与“时间”之间的区别很重要。当时间复杂性是主题时，重要的是不要将“时间”的用法与“花费毫秒的时间”混淆起来。

恒定时间的定义是什么？

在许多情况下，维基百科经常被认为是一个不好的参考，但在这种情况下（和许多其他），可用的定义是正确的，并且将有助于描述事情的工作方式。

关于时间复杂性的文章说了如下关于时间的问题：

维基百科 - 恒定时间

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

由于插入std::list不依赖于std::list中元素的数量，我们说插入是恒定时间; 无论何时何地，每次插入由相同数量的基本操作组成; 没有一个与列表的大小有关。

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

说实话，这并不重要，即使new的复杂性隐含地取决于我们已经分配了多少个先前的实体，我们列表插入的复杂性将保持不变。分配对列表的大小无关紧要。

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

我们列表中的路径全部包括operator new 。路径不会因为我们列表的大小而改变，路径的复杂性是恒定的时间。

那么我们在处理什么？

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

尽管这个句子可能有点误导，但它的作用在于解释插入是怎样的O(1) ，尽管算法的一部分不是恒定时间。

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

这是一个非常棘手的问题，在这个线程中已经讨论了很多。

如果我可以试着总结一下：标准有一些微妙的区别。如果你仔细阅读，有些操作确实被指定为“恒定时间”，但std::list插入不在其中。它被指定为“常量”（编辑：错误，见下文）和“通用容器要求”条款（本C ++标准草案中的23.2.1）解释了

本条款中的所有复杂性要求仅以包含对象的操作数量表示。

（编辑：FilipRoséen指出，我错了; std::list插入被指定为“恒定时间”，但我认为通用要求条款仍然适用）。因此，因为列表插入只能在单个对象及其邻居上工作，即使它不一定是“恒定的时间复杂度”，也是“恒定的复杂度”，因为分配没有时间复杂性保证。

实际上，一个体面的内存分配器在分配的对象数量上并不是线性的，尽管它也可能不是恒定的时间。

链接地址: http://www.djcxy.com/p/78271.html