k路合并的时间复杂度是多少?

Wikipedia article O(log(n)) 找到敏是谁 O(1) . 我们首先将每个数组的第一个元素插入堆中。这需要 ∑log(i) 时间, i = 0 to k - 1 或 O(klog(k)) O(log(k!)) )

然后移除min元素,并从数组中插入下一个元素 min元素最初来自何处。这需要 O(1) + O(log(k)) 时间,我们重复一遍 n - 1 次。

O(klog(k)) + O(n - 1) + O((n - 1)log(k)) ≅ O(klog(k)) + O(n) + O(nlog(k))