"恒定"复杂性究竟意味着什么？时间？副本/动作的数量？

Question

我可以想到C++中的三个操作可以在某种意义上描述为具有"恒定"的复杂性.我已经看到了一些关于这意味着什么的辩论(*),在我看来,我们可以说"所有这些操作都是不变的,但有些操作比其他操作更稳定":-)

(编辑2:如果你已经认为你已经知道了答案,那么请先阅读一些关于这个问题的辩论,然后再过早说: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,但它仍然被称为常量(摊销).平均而言,向向量添加大量数据将带来与添加量无关的复杂性,这就是为什么它被称为"摊销常数"时间.(我对吗？)

最后,我要求int避免使用其他类型的复杂性.例如,a vector< vector<int> >可能稍微复杂一点,因为向量(向量)的每个元素可能具有不同的大小,例如,交换两个元素并不像上面的情况1那样恒定.但理想情况下,我们可以回答所有人vector<T>,而不仅仅是T=int.

(*)有关辩论的一个例子,请参阅对这些答案的评论:究竟什么数据结构是C++中的deques？

Answer 1

始终相对于特定变量或变量集声明复杂性.因此,当标准谈到恒定时间插入时,它谈论的是相对于列表中项目数的恒定时间.也就是说,O(1)插入意味着列表中当前的项目数不会影响插入的总体复杂性.该列表中可能包含500或50000000个项目,插入操作的复杂性将相同.

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

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

这意味着我们可以随心所欲地实现我们的算法,包括在任何实用意义上时间不是真正恒定的算法,而是我们尊重所包含对象上"操作"的数量.

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

如上所述,您可以std::list使用与删除相关的内存分配器O(log(n))(其中n是分配数).但是,相对于列表中的项目数,删除列表中的元素仍然是O(1).

不要将复杂性与整体性能混淆.复杂性的目的是为不同变量的算法提供一般度量.程序员希望他们的代码快速运行的目的是找到一种合理的算法实现,该算法符合实现该性能所需的复杂性.

复杂性是评估算法效率的工具.复杂性并不能意味着你停止思考.

什么'摊销'是什么意思？

摊销意味着:

如果某些内容是"按时间分摊",那么当您在同一数据结构上无限次重复操作时,复杂性限制在X.

因此,std::vector在后方进行"摊销恒定时间"插入.因此,如果我们接受对象并对其执行无限多次插入,复杂度的渐近极限将与"恒定时间"插入没有区别.

在外行人看来,这意味着操作有时可能是不恒定的,但是它将是非常数的次数总是会减少.从长远来看,它是恒定的时间.