Jac*_*ale 4 arrays algorithm time-complexity
假设有一个未排序的数组A,它包含一个元素x(x是元素的指针),每个元素都有一个卫星变量k.因此,我们可以获得以下时间复杂度(对于最坏的情况):
如果我们想要搜索特定的K,那么它需要花费O(n).
如果我们想要插入一个元素,那么它的成本为O(1),因为A只是将元素添加到结尾.
如果我们知道x,然后从数组A中删除它会怎么样？
我们必须首先搜索 xk并获取x的索引,然后通过A中的索引删除 x,对吗？
所以对于删除,它也花费O(n),对吧？
谢谢
Jer*_*fin 25
查找具有给定值的元素是线性的.
由于数组未进行排序,因此您可以在固定时间内进行删除.首先将要删除的元素交换到数组的末尾,然后将数组大小减少一个元素.
小智 5
恩，那就对了。此外，如果它是一个数组，单独删除将需要O(n)时间，因为在删除元素后，您需要将该元素右侧的所有元素向左移动一个位置。因此，即使您知道 x（例如，您只会删除第一个元素），也需要O(n)时间。