作者lars247247 (lars)
看板Grad-ProbAsk
标题Re: [问题] Quick sort VS Merge sort
时间Fri May 15 21:51:52 2009
※ 引述《dar23 (dar23)》之铭言：
: 请问这两个sort同样是divive & conquer策略
: 为啥quick sort的space complexity只需Big-O(1)
: 而merge sort却需Big-O(n)?
: 这是教授问我的问题.......
我记得是因为你用Quick的时候,你并不用额外去建造一个空间去暂存你那些已经排序好
的东西,所以他的空间复杂度是N( 1 )
但是Merge不一样,他每次执行都会先将原始阵列分割成等份大小,然後制造出一个跟分割阵列
一样大小的空间,已用来暂存那些已经排好序的资料,然後再将那些分割过且排序好的资料
在一次整合起来,所以他的空间复杂度会随着原始阵列大小而有所变化
不知道这样讲你懂吗??
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 219.71.109.21
1F：推 FRAXIS:quicksort要考虑递回用的stack.. 这样就不会是O(1)了.. 05/16 07:43
2F：→ FRAXIS:Merge sort已经有人改良出O(1)空间的方法 只是不简单就是了 05/16 07:44