算法 - 未排序数组中删除操作的时间复杂度

Question

假设有一个未排序数组A，并且它包含一个元素x（x是元素的指针），每个元素都有一个附属变量k。因此，我们可以得到以下时间复杂度（针对最坏情况）：

如果我们想要搜索特定的K，则需要耗费O(n)。

如果我们想要插入一个元素，则需要耗费O(1)，因为A将元素添加到末尾。

那么如果我们知道x，如何从数组A中删除它？

我们必须先搜索x.k并获取x的索引，然后通过其在A中的索引删除x，对吧？

因此，对于删除操作，也需要耗费O(n)对吧？

谢谢

- Jackson Tale

Answer 1

给定值的元素查找是线性的。

由于数组本身并未排序，因此可以在常数时间内执行删除操作。首先将要删除的元素与数组末尾的元素交换位置，然后减少数组大小一个元素。

- Jerry Coffin

---

这很酷。但你不能像那样实现一个通用的删除，因为尽管数组未排序，它仍然可能具有需要保留的某些特定顺序。 - dan-gph

@Dangph：这仍然是排序的，只是不是按升序（或降序）排序。 - Jerry Coffin

@Jerry：我认为作者通常会区分“有序”和“排序”。一个“排序”的数组是指其顺序取决于其中对象的值。即使重要的是保留插入时间顺序，按插入时间排序的数组通常也不被描述为“排序”。 - Steve Jessop

话虽如此，提问者在没有进一步的评论的情况下将数组称为“未排序”，因此我认为在证明其他情况之前，假设顺序不重要是公平的。 - Steve Jessop

在大多数典型情况下（例如C++的vector或Java的ArrayList），删除集合中间的元素不会改变其余元素的顺序，因此它们必须移动所有其他元素以填补空洞。 - Jerry Coffin

Answer 2

没错。如果是数组，仅仅删除一个元素就需要花费 O(n) 的时间，因为在你删除这个元素之后，你还需要将这个元素右侧的所有元素向左移动一位。所以，即使你知道 x（比如说，你只想删除第一个元素），也需要花费 O(n) 的时间。

- Sabbir Yousuf Sanny

Answer 3

在排序数组中，删除操作的最坏时间复杂度为O(n)， 如果数组未排序，并且在删除操作之后提到数组的顺序不应更改，则时间复杂度将与O(n)相同， 否则它将是O(1)。

- Parveen Kumar

Answer 4

未排序的数组

例如：

Items Value     [3,   5,  1,  7,  4]
Items Address   [&1, &2, &3, &4, &5]
Deleting - Value 5

1. 删除 - 保持顺序 - O(n + n) - O(2n) ~> O(n)

i) O(n) - 找到该元素的位置（值为5的索引=1）

ii) O(n) - 删除该元素后，其余项目（1、7、4）需要重新排序以保持先前项目的地址。像这样：

Items Value     [3,   1,  7,  4]
Items Address   [&1, &2, &3, &4]

2. 删除 - 不保留顺序 - O(n + 1 + 1) - O(2 + n) ~> O(n)

i) O(n) - 查找该元素的位置（值为5的索引=1）

ii) O(1) - 与数组的最后一个元素交换。

Items Value     [3,   4,  1,  7,  5]
Items Address   [&1, &2, &3, &4, &5]

iii) O(1) - 删除数组的最后一个元素。

Items Value     [3,   4,  1,  7]
Items Address   [&1, &2, &3, &4]

- Vinoth Anandan

Answer 5

是的。查找要删除的元素需要 O(n) 时间。然后，为了删除它，您必须将其右侧的所有元素向左移动一个空格。这也是 O(n)，因此总复杂度是线性的。

此外，如果您正在讨论静态分配的数组，则插入也需要 O(n)。您必须调整数组大小以容纳额外的元素。虽然有方法将此运行时间摊销为 O(1)。

- tskuzzy

---

由于数组未排序，因此实际上您不必移动任何内容，只需使用最后一个元素填补空缺即可。 - Aurelien Ribon