algorithm - 对 ⌈logn⌉ 已排序的 ⌊n/logn⌋ 元素列表中的所有元素进行排序的时间复杂度是多少？

Question

假设每个有 ⌈n/logn⌋ 元素的 ⌈logn⌉ 排序列表。生成所有这些元素的排序列表的时间复杂度是：（提示：使用堆数据结构）

A. O(nloglogn)

B. Θ(nlogn)

C. Ω(nlogn)

D. Ω(n3/2)

我的理解：

有一个 logn 列表，每个都包含 n/logn 元素，然后我们可以应用最小堆过程，每个列表都可以在 O(n/logn) 中完成。现在我们有了满足最小堆属性的登录列表。现在我怎么能进一步理解它我真的很困惑。请帮我想象一下。

标签： algorithmtime-complexity

Answer 1

[我假设我们正在按递增顺序排序]

为每个列表的最小（即：第一个）元素构建一个堆，（并且对于每个列表以及值，记录它来自哪个列表的哪个索引）。反复删除此堆的最小元素，然后将下一个元素插入它来自的列表中（如果该列表尚未被使用）。这为您提供了所有元素的排序列表。

这个堆有 [log(n)] 个元素，所以构建这个堆的初始成本是 O(log(n))，每次删除和插入需要 O(log(log n)) 时间。所以总的来说，这种排序的成本是 O(log(n) + nlog(log n)) = O(nloglogn)。