作者AAQ8 ()
看板Grad-ProbAsk
標題[理工] 資結題庫
時間Thu Jan 10 15:17:48 2019
https://i.imgur.com/5P19VRF.jpg
這題的B小題
為什麼call merge sort的次數是2次
如果照下面那樣做的話不是3次嗎
另外想問quick sort是in place嗎
洪逸上課筆記裡寫不是in place的是merge sort和非comparison base的排序
不過我看quick sort的空間複雜度是O(logn)~O(n)
所以不知道quick sort是不是in place
麻煩各位 謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.26.79.158
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1547104671.A.BD9.html
1F：推 BroccolYee: 只有4,5 1,2算swap 剩下都是兩個串列擺前後直接合併 01/10 17:09
2F：→ BroccolYee: 另外quick sort的空間複雜度是call遞迴stack的層數 01/10 17:10
3F：→ BroccolYee: 它依然是in-place 01/10 17:10
4F：推 FRAXIS: Quicksort 算不算 inplace 取決於你 inplace 的定義 01/10 22:55
5F：→ FRAXIS: 如果你定義 inplace 是最多只能用 O(1) 額外空間，那 01/10 22:56
6F：→ FRAXIS: quicksort 就不是 in-place 01/10 22:58
7F：→ FRAXIS: 不過因為 quicksort 有一種版本可以最多只使用O(lg n) 01/10 22:58
8F：→ FRAXIS: 空間 所以很多人也認為 quicksort 是 in-place 01/10 22:59
9F：→ FRAXIS: 理論上 quicksort 可以只使用 O(1) 空間，只是方法很複雜 01/10 22:59
10F：→ FRAXIS: 所以教科書上也不會提 01/10 23:00
11F：推 kyrie77: 推F大 01/11 05:15