arrays - 排序数组中的时间复杂度

Question

给定一个降序排列的数组，从这个数组中删除最小元素的时间复杂度是多少？

=================================================

我的最小元素将在最后一个位置，所以 O(n) 找到它？或者我应该应用二进制搜索，因为数组已排序，或者只是 O(1) 到达最后？

标签： arraysdata-structures

Answer 1

这实际上取决于您的意思是“从数组中删除”。您有一个按降序排序的数组，并且您想要删除最小元素。

假设数组是[5, 4, 3, 2, 1]. 你知道数组有多大，所以找到最小元素是 O(1)。你只需索引a[a.length-1].

但是删除最后一个元素是什么意思呢？您可以轻松地将那里的值替换为哨兵值，表示该位置不再使用，但是下次您尝试获取最小元素时，您必须访问a[a.length-1]，然后进行反向扫描以找到第一次使用的元素。当您删除更多项目时，这接近 O(n)。

或者您是否保留一个计数器来告诉您数组中实际使用了多少个值？因此，您将有一个变量 ,count来告诉您哪个是最后一个元素。当您想获得最小的元素时：

smallest = a[count];
count = count-1;

这仍然是 O(1)，但它会在数组中留下未使用的项目。

但是，如果要确保数组长度始终反映其中的项目数，则必须重新分配数组以使其更小。即 O(n)。

因此，您的问题的答案是“视情况而定”。