时间复杂度 - 在动态数组中间插入一个项目

Question

我看到这篇关于动态数组时间复杂度的文章，它澄清了很多。不过我有一个基于案例的问题。假设我有一个总共有 6 个元素的动态数组，并假设删除了第 4 个元素。在这种情况下，删除复杂度将是，O(n-index)因为O(6-4) = 2最后两个元素只需要向上移动。它是否正确 ？我有一些文章给出了最坏情况的复杂度，说如果删除最上面的元素，那么时间复杂度将为O(n)。我找不到任何有关从中心删除/插入项目的内容。

Answer 1

您对需要移动的物品数量的分析是正确的。然而，用大 O 表示法来说，这仍然是 O(n)。如果列表中有n 个项目并从中间删除某些内容，则必须移动 *0.5 * n* 个项目。但是在处理大 O 时，我们删除了任何常数乘数，因此只剩下O(n)。