python - python中heapq.merge的时间复杂度是多少？
问题描述
我读到 heapq.merge 函数专门用于合并2个排序数组？时间复杂度是 O(n)？如果不是，那是什么，为什么？还有它的空间复杂度是多少。
我正在解决用 2 个指针合并 2 个排序数组的问题，并且可以实现 O(n) 时间复杂度和 O(n) 空间复杂度。
解决方案
如果要合并 K 个排序数组并且每个数组有 N 个元素，那么 heapq.merge 将以 NK(logK) 的时间复杂度执行操作。因为 NK 是所有 K 个数组中元素的总数，并且每个元素都必须进行比较。而 logK 是从堆顶部（即堆的高度）开始的冒泡操作的时间复杂度。
在你的情况下K = 2，log（2）= 1。所以在你的特殊情况下它是O（n）