algorithm - 寻找合并排序列表的算法

Question

问题如下:有 k 个长度为 n/k 的排序列表(我们假设 k 除以 n)。我需要找到一种算法，将这些列表合并为一个长度为 n 的列表运行时间复杂度为 O(k + nlogk)。

我正在考虑按情侣合并列表，而不是按夫妇再次合并合并的列表，依此类推，当我到达长度为 n 的单排序列表时，我停止了。

当我计算我的算法的时间复杂度时，我得到了 O(nlogk)，这比所需的时间要好。

我在想是不是我的方法不对。感谢您的帮助!

Answer 1

你的方法很好。

当给定 k<=n 且 k>=1 时，则 O(n log k) = O(k + n log k)。 “我们假设 k 除以 n”这一陈述暗示了这两者，因此您的结果就是它们应该是的结果。

如果我们放宽这些条件，那么我们必须考虑 k>n 的情况，并且其中 k 个列表为空。然后你必须担心合并所有这些空列表所花费的时间，而你的算法需要 O(k + n log k) 时间。