对排序列表的排序数组进行操作的时间复杂度

Question

我有一个排序数组，其中 N 个元素平均分布在 K 个列表中，该数组也已排序。什么是时间复杂度（以最严格的 Big-O 表示法）：

正在删除最小的元素。
删除最小元素后重新排序数组。
删除所有 N 个元素

对于第一部分，我认为答案是 O(1)，因为最小的元素是第一个元素。但是它所属的列表不一定是第一个列表，所以我不确定。

对于第二部分，我不确定（也许O(NK)？）

对于第三部分，它必须是 O(N)，因为我们要遍历整个数组，但我还是不确定

Answer 1

这取决于你说 "K lists [are] also sorted" 时的意思。

如果数字随机分布在K个列表中，但是每个K个列表本身都是排序的，那么查看头部需要O(K)时间所有列表中的最小元素。但是，如果数字在 K 个列表之间划分，那么 K 个列表 A,B,C,... 可以这样排序 A0<=AN< =B0<=BN<=C0<=CN...，那么找到最小元素需要 O(1) 时间，因为你知道它在第一个列表的头部。

删除数组中最小或最大的元素会保留现有的排序顺序，因此这需要时间 O(1)。

"remove" 所有元素所需的时间取决于您的计算模型。如果删除算作简单地处理整个数据结构，则可能需要 O(1) 时间。但是，如果每个元素都需要单独清理，则需要 O(N+K) 时间： O(N) 成本访问每个元素的成本和访问每个列表的成本 O(K)。

Answer 2

具体的例子有帮助。假设您有三个列表（数组）：

[7, 11, 15]
[3, 12, 19]
[2, 4, 6]

删除最小的项目需要您先找到它。各个列表是有序的，但列表的列表不是。找到最小的项目需要 O(K) 的时间，因为你必须对列表的列表进行顺序扫描。

找到最小项后，将花费 O(m) 时间（其中 m 是包含最小项的列表的大小）将其删除。原因是当您从列表中删除第一项时，所有其他项都必须向上移动。即：

[2, 4, 6]变成了[_, 4, 6]，然后你就得把东西往上移才能变成[4, 6, _]。（_ 表示空值，或者您用来表示 "no value." 的任何标记值）

我想你可以说删除是 O(1)，然后重新排序数组是 O(m)。

您可以在 O(N) 时间内删除所有元素，前提是您不关心删除它们的顺序。如果要移除所有排序好的元素，那么复杂度就是O(n * K)，因为每次都要找到最小的元素。您可以通过实施 K 路合并将其改进为 O(n * log(K))，但代价是 O(K) 额外内存。

对排序列表的排序数组进行操作的时间复杂度

Time complexity of operations on a sorted array of sorted lists

arrays

time-complexity

heap

theory