假设有一个未排序的数组A，它包含一个元素x（x是元素的指针），每个元素都有一个卫星变量k。因此，我们可以获得以下时间复杂度（对于最坏的情况）：
如果我们想要搜索特定的K，那么它需要花费O（n）。
如果我们想插入一个元素，那么它需要花费O（1），因为A只是将元素添加到结尾。
如果我们知道x，然后从数组A中删除它会怎么样？
我们必须首先搜索x.k并获取x的索引，然后通过A中的索引删除x，对吗？
所以对于删除，它也花费O（n），对吧？
谢谢
查找具有给定值的元素是线性的。
由于数组未进行排序，因此您可以在固定时间内进行删除。首先将要删除的元素交换到数组的末尾，然后将数组大小减少一个元素。
恩，那就对了。此外，如果它是一个数组，单独删除将需要O(n)时间，因为删除元素后，您需要将该元素右侧的所有元素移到左侧一个位置。因此，即使您知道x（例如，您只会删除第一个元素），也需要O(n)时间。
是。需要O(n)时间才能找到要删除的元素。然后，为了删除它，您必须将所有元素向左移动一个空格。这也是O(n)所以总复杂度是线性的。
此外，如果您正在讨论静态分配的数组，插入也需要O(n)。您必须调整数组的大小才能容纳额外的元素。有一些方法可以将这个运行时间分摊到O(1)。