c – “不变”的复杂性是什么意思？时间？份数/动作数
|
我可以想到C中的三个操作,可以在某种意义上被描述为具有“不变”的复杂性.我已经看到了这个意思的一些辩论(*),在我看来,我们可以说“所有这些操作是不变的,但有些比其他人更为常态”:-)
(编辑2：如果你已经认为你知道答案,请阅读这个问题的一些辩论,然后才赶上：What data structure,exactly,are deques in C++?很多人,相当高分,都在争论“不变”的意思,我的问题是,你可能会觉得很明显！) (编辑：我不需要一个“复杂性”的引言,我想要一个明确的答案,也许是从C标准的引用,告诉我们应该是什么是不变的.处理器刻度,现实世界的时间,或者其他的东西？在其他线程上,有些人认为时间与C标准所要求的完全无关.) 标准中的这些复杂性保证是否适用于操作的运行时？或者他们只是指定可能发生的包含的对象的(最大)份数/移动数量？ “摊销”是什么意思？ 给定(非空)向量< int> v,以下在运行时显然是常数： swap(v.front(),v.back()); (尽管可能会指出,这取决于数据是在缓存还是交换出来,或者是什么！). 给定一个列表< int> l,做一个push_back很简单.正确分配一个新项目,并且链接列表中的几个指针被混洗.每个push_front涉及一个分配,总是具有相同的内存量,所以这显然是相当“恒定的”.但是,当然,分配时间可能相当可观.内存管理可能需要花费大量的时间才能找到合适的可用内存. 3.但是在向量< int>上执行push_back更不可预测大多数情况下,它将非常快速,但是现在每个数据都必须重新分配所有数据的空间,并将每个元素复制到一个新的位置.因此,在运行时方面比单个列表:: push_front不太可预测,但它仍被称为常量(摊销).平均来说,向向量中添加大量数据将需要独立于添加量的复杂性,这就是为什么称为“摊销常数”时间. (我对吗？) 最后,我问了int来避免另一种类型的复杂性.例如,矢量<诠释> >由于向量(向量)的每个元素可能具有不同的大小,并且例如交换两个元素并不完全如上述情况1.一样,因此可能会更复杂一点.但理想情况下,我们可以回答所有向量T,而不是T = int. (*)有关辩论的例子,请参阅这些答案的意见：What data structure,are deques in C++? 解决方法
复杂性总是相对于特定变量或变量组而言.所以当标准谈论定时插入时,它谈论的是与列表中项目数量相关的恒定时间.也就是说,O(1)插入意味着列表中当前的项目数量不会影响插入的整体复杂度.该列表可能有500或50000000个项目,并且插入操作的复杂性将是相同的.
例如,std :: list具有O(1)插入和删除;插入的复杂性不受列表中元素数量的影响.然而,内存分配器的复杂度可能取决于已经分配的事情的数量.但是,由于O(1)正在谈论清单中的项目数量,所以并不涵盖.因此,我们将会测量内存分配器的复杂性,而不是数据结构. 简而言之：这是一个不同的测量.
没有相对于实现来指定复杂性.它是相对于算法指定的.上下文可以切换并不重要,因为运行时间不是复杂性. 如上所述,您可以使用相对于删除(其中n是分配数)的O(log(n))的内存分配器实现std :: list.但是,删除列表中的元素仍然是O(1)相对于列表中的项目数. 不要将复杂性与整体性能混淆.复杂性的目的是为不同变量的算法提供一般的度量.希望代码快速运行的程序员的目的是找到符合实现该性能所需的复杂性的算法的合理实现. 复杂性是评估算法效率的工具.复杂性并不意味着你会停止思考.
Amortized表示： 如果某些东西是“摊销X时间”,那么当您在相同的数据结构上重复无限次的操作时,X处的复杂性限制 所以,std :: vector在后面有“摊余时间”插入.因此,如果我们采取对象并在其上执行无限多的插入,则渐近的复杂性限制将与“常时”插入无异. 在外行方面,这意味着这个操作有时可能是不恒定的,但是它将不常数的次数将总是在减少.在长期的插入中,它是不变的时间. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |