时间复杂度-在动态数组的中间插入一个项
时间复杂度-在动态数组的中间插入一个项
提问于 2015-07-03 20:49:55
我遇到了这个关于动态数组的时间复杂性的article，它澄清了许多问题。然而，我有一个基于案例的问题。假设我有一个动态数组，它总共有6个元素，并且假设第4个元素被移除。在这种情况下，删除复杂性将是O(n-index)，这将是O(6-4) = 2，因为最后两个元素只需要向上移动。这是对的吗？我有一些文章给出了最坏的情况复杂性，说如果去掉了最上面的元素，那么时间复杂度将是O(n)。我找不到关于从中间删除/插入项目的任何内容。
回答 1
Stack Overflow用户
回答已采纳
发布于 2015-07-03 20:53:24
您对需要移动的项目数的分析是正确的。然而，在大O表示法中，这仍然是O(n)。如果列表中有n项并从中间移除某项，则必须移动*0.5 * n*项。但是，在处理大O时，我们去掉了任何常数乘子，所以这就是O(n)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/31214057
复制相关文章
相似问题
腾讯云开发者
