一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 338|回复: 3
收起左侧

[树/链表/图] 请教 Merge k Sorted Lists 空间复杂度问题

[复制链接] |试试Instant~ |关注本帖
oio14644 发表于 2015-11-4 14:35:05 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
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)。


请教这个帖子里面分析的空间复杂度是正确的吗?
谢谢
JamesJi 发表于 2015-11-4 21:02:12 | 显示全部楼层
我觉得是对的
回复 支持 反对

使用道具 举报

plich 发表于 2015-11-5 00:23:40 | 显示全部楼层
分析的没问题……归并法只是和归并排序类似而已
如果你对链表写归并排序,空间一样是O(logn)
回复 支持 反对

使用道具 举报

 楼主| oio14644 发表于 2015-11-5 01:39:14 | 显示全部楼层
plich 发表于 2015-11-5 00:23
分析的没问题……归并法只是和归并排序类似而已
如果你对链表写归并排序,空间一样是O(logn)

thanks, 可以认为merge sort 比用heap 更优一些:时间复杂度一样,空间复杂度更小
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 06:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表