作者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