一亩三分地论坛

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

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

[Leetcode] 询问一道 Merge K Sorted List 题目的分析

[复制链接] |试试Instant~ |关注本帖
pyx115 发表于 2015-6-23 00:16:42 | 显示全部楼层 |阅读模式

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

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

x
## Question:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

## 我的问题:

这是我根据CleanCodeHnadBook上面答案写的解法,即不断的合并两个lists:
  1. def mergeKLists(self, lists):
  2.         lists = [list for list in lists if list]
  3.         if not lists:
  4.             return None
  5.         end = len(lists) - 1
  6.         while end > 0:
  7.             begin = 0
  8.             while begin < end:
  9.                 lists[begin] = self.merge(lists[begin], lists[end])
  10.                 begin += 1
  11.                 end -= 1
  12.         return lists[0]

  13.     def merge(self, lis1, lis2):
  14.         dummyHead = ListNode(0)
  15.         p = dummyHead

  16.         while lis1 and lis2:
  17.             if lis1.val < lis2.val:
  18.                 p.next = lis1
  19.                 p = p.next
  20.                 lis1 = lis1.next
  21.             else:
  22.                 p.next = lis2
  23.                 p, lis2 = p.next, lis2.next
  24.         if lis1: p.next = lis1
  25.         if lis2: p.next = lis2
  26.         return dummyHead.next
复制代码
时间应该是O(nklogk)。

而另一种解法,先把所有node的值取出来排序,再赋值到一条新建的list去:
  1. def mergeKLists(self, lists):
  2.     lists = [list for list in lists if list]
  3.     if not lists:
  4.         return None

  5.     lis = []
  6.     for head in lists:
  7.         while head is not None:
  8.             lis.append(head.val)
  9.             head = head.next
  10.     lis.sort()

  11.     dummyHead = ListNode(0)
  12.     p = dummyHead
  13.     for val in lis:
  14.         p.next = ListNode(val)
  15.         p = p.next
  16.     return dummyHead.next
复制代码
我查了python 的 list 的 sort()是O(nlogn),对于此题目来说应该是O(nk log(nk) )。应该是比第一种解法慢的,但是实际上第一种解法用时504ms,第二种用时136ms,第二种远快于第一种,搞不明白为什么?是我复杂度分析有误还是什么问题?
invisibili 发表于 2015-6-23 00:38:59 | 显示全部楼层
本帖最后由 invisibili 于 2015-6-23 11:56 编辑

感觉第一个不是O(nklogk) 像是(2^k)*n
------------------------------------------
第一个应该是nk^2
你的merge算法是O(n+m)的 m,n是list长度
具体是n+n + 2n+n + 3n+n + ... + (k-1)n+n = O(nk^2)
             1          2           3                   k-1
可以用不同的k试一下 看一下时间增长趋势


回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-23 11:31:46 | 显示全部楼层
复杂度分析是对的。具体的执行时间不需要太过关注。之所以后者实际上要快的原因可能主要在sort上:

1. Python的sort是Timsort,这种算法的最佳时间复杂度是O(N),特别在数组有大量已经排序好的部分时(而这正是此题的情况)。所以,实际比较次数可能是小于O(NlogN)的。

2. Python的sort通常是用C写成的。所以即使复杂度更大,但是在N不是特别大的情况下,很有可能其实际执行速度快于你自己用pyton写的merge。

你可以尝试一下自己拿Python写一个Quicksort,取代自带的sort,然后再来比较一下运行时间。


评分

1

查看全部评分

回复 支持 反对

使用道具 举报

robinho364 发表于 2015-6-23 13:18:53 | 显示全部楼层
stellari 发表于 2015-6-23 11:31
复杂度分析是对的。具体的执行时间不需要太过关注。之所以后者实际上要快的原因可能主要在sort上:

1. P ...

不错,有理有据,长姿势了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 21:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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