作者dar23 (dar23)
看板Grad-ProbAsk
标题[问题] Quick sort VS Merge sort
时间Thu May 14 22:16:13 2009
请问这两个sort同样是divive & conquer策略
为啥quick sort的space complexity只需Big-O(1)
而merge sort却需Big-O(n)?
这是教授问我的问题.......
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.131.73.198
1F：→ f31816:主要是因为quick sort是只用交换就可以排序完成 05/15 02:15
2F：→ f31816:空间只需O(1) 而Merge sort需要额外的space来排序 05/15 02:16
3F：→ dar23:quick sort是否在特别情形下才会O(1)呢? 05/15 10:16
4F：推 f31816:任何情况皆是O(1) 他不需要额外的空间辅助排序 05/15 10:22
5F：推 sasbluesea:qsort可以在原本的阵列排序 05/15 10:58