从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)).