请教 Merge k Sorted Lists 空间复杂度问题

http://blog.csdn.net/linhuanmars/article/details/19899259

归并算法 我们来分析一下上述算法的时间复杂度。假设总共有k个list，每个list的最大长度是n，那么运行时间满足递推式T(k) = 2T(k/2)+O(n*k)。根据主定理，可以算出算法的总复杂度是O(nklogk)。如果不了解主定理的朋友，可以参见主定理-维基百科。空间复杂度的话是递归栈的大小O(logk)。
我看归并算法的空间复杂度是线性的O(n)的
https://zh.wikipedia.org/zh-cn/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F


这种方法用到了堆的数据结构，思路比较难想到，但是其实原理比较简单。维护一个大小为k的堆，每次取堆顶的最小元素放到结果中，然后读取该元素的下一个元素放入堆中，重新维护好。因为每个链表是有序的，每次又是去当前k个元素中最小的，所以当所有链表都读完时结束，这个时候所有元素按从小到大放在结果链表中。这个算法每个元素要读取一次，即是k*n次，然后每次读取元素要把新元素插入堆中要logk的复杂度，所以总时间复杂度是O(nklogk)。空间复杂度是堆的大小，即为O(k)。


请教这个帖子里面分析的空间复杂度是正确的吗？
谢谢

我觉得是对的

分析的没问题……归并法只是和归并排序类似而已
如果你对链表写归并排序，空间一样是O(logn)

plich 发表于 2015-11-5 00:23
分析的没问题……归并法只是和归并排序类似而已
如果你对链表写归并排序，空间一样是O(logn)

thanks, 可以认为merge sort 比用heap 更优一些：时间复杂度一样，空间复杂度更小