时间戳

首页 > 解决方案 > 排序列表的排序数组上的操作的时间复杂度

arrays - 排序列表的排序数组上的操作的时间复杂度

问题描述

我有一个 N 个元素的排序数组，它们平均分布在 K 个列表中，也被排序。以下情况的时间复杂度（以最严格的 Big-O 表示法）是多少：

  1. 删除最小的元素。
  2. 删除最小元素后重新排列数组。
  3. 删除所有 N 个元素

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

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

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

标签： arraystime-complexityheaptheory

解决方案

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

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

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

一旦你找到了最小的项目，将需要 O(m) 时间（其中 m 是包含最小项目的列表的大小）来删除它。原因是当您从列表中删除第一个项目时，所有其他项目都必须向上移动。那是：

[2, 4, 6]变成[_, 4, 6]了，然后你就得搬东西了[4, 6, _]。（_表示空值，或您用来表示“无价值”的任何标记值。）

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

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

推荐阅读