→ f31816:主要是因為quick sort是只用交換就可以排序完成 05/15 02:15
→ f31816:空間只需O(1) 而Merge sort需要額外的space來排序 05/15 02:16
→ dar23:quick sort是否在特別情形下才會O(1)呢? 05/15 10:16
推 f31816:任何情況皆是O(1) 他不需要額外的空間輔助排序 05/15 10:22
推 sasbluesea:qsort可以在原本的陣列排序 05/15 10:58
請問這兩個sort同樣是divive & conquer策略
為啥quick sort的space complexity只需Big-O(1)
而merge sort卻需Big-O(n)?
這是教授問我的問題.......
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.131.73.198