algorithm - 按最大元素对 k 个排序列表进行排序

Question

如果我有 k 个排序的单链表并按每个列表的最大元素(列表中的最后一个)对它们进行排序(合并排序)，那么大 O(运行时间/时间复杂度)会是多少？假设列表 1 ~ k 有不同的大小:n_1 ~ n_k。我在想 O(k * log(MAX(n_1 ~ n_k))) 但不确定我是如何或为什么想到这种思路的。

Answer 1

假设你有 O(k) 个内存单元来存储每个列表的最大元素，合并排序列表本身的时间，即不合并它们的元素，将是 O(sum(N_i) + k*log k).

有第一项是因为您需要恰好导航到每个列表的末尾一次；之后，您可以使用最大值“标记”列表，并对标记列表执行合并排序。第二项来自使用合并排序对 k 个项目进行排序。原始列表已排序这一事实变得无关紧要，因为无论如何您都需要遍历整个列表。

如果列表是可修改的，即使没有额外的存储，时间复杂度也会保持不变，因为您可以反转列表，对它们进行排序，然后再次反转它们。反转列表需要 O(sum(N_i))，因此时间复杂度将保持不变。