algorithm - 从 n 个排序数组中获取 k 个最小值的时间复杂度？

Question

我有 n 个数组。这些数组中的每一个都可以是无限长的。 (长度可以是可变的)。所有这 n 个数组都已排序。

现在我想从这 n 个排序的数组中取出前 k 个最小的元素。

例如 n=5 和 k=10

2 4 6 7 9 

23 45 67 78 99

1 2 6 9 1000 4567 6567 67876

45 56 67 78 89 102 103 104

91 991 9991 99991 

现在答案应该是 1 2 4 6 7 9 23 45 56 67

会不会是 O(n*k)，即最坏情况下为 O(n^2)，最好情况下为 O(k)？

Answer 1

我认为是 O(n + k.log(n))。

首先在每个数组中建立一个最小元素的堆(也存储数组的索引)。构建大小为 n 的堆是 O(n)。然后，重复 k 次:从堆中取出一个元素(复杂度为 O(log n))，然后从您取出的元素所在的数组中插入下一个最小元素(也为 O(log n))。总的来说，这是 O(n + k.log(n))。