[理工] 資結題庫

看板Grad-ProbAsk作者時間5年前 (2019/01/10 15:17), 編輯推噓3(3推 0噓 8→)
留言11則, 3人參與, 5年前最新討論串4/5 (看更多)
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1547104671.A.BD9.html
推
01/10 17:09, 5年前 , 1F
只有4,5 1,2算swap 剩下都是兩個串列擺前後直接合併
01/10 17:09, 1F
→
01/10 17:10, 5年前 , 2F
另外quick sort的空間複雜度是call遞迴stack的層數
01/10 17:10, 2F
→
01/10 17:10, 5年前 , 3F
它依然是in-place
01/10 17:10, 3F
推
01/10 22:55, 5年前 , 4F
Quicksort 算不算 inplace 取決於你 inplace 的定義
01/10 22:55, 4F
→
01/10 22:56, 5年前 , 5F
如果你定義 inplace 是最多只能用 O(1) 額外空間，那
01/10 22:56, 5F
→
01/10 22:58, 5年前 , 6F
quicksort 就不是 in-place
01/10 22:58, 6F
→
01/10 22:58, 5年前 , 7F
不過因為 quicksort 有一種版本可以最多只使用O(lg n)
01/10 22:58, 7F
→
01/10 22:59, 5年前 , 8F
空間 所以很多人也認為 quicksort 是 in-place
01/10 22:59, 8F
→
01/10 22:59, 5年前 , 9F
理論上 quicksort 可以只使用 O(1) 空間，只是方法很複雜
01/10 22:59, 9F
→
01/10 23:00, 5年前 , 10F
所以教科書上也不會提
01/10 23:00, 10F
推
01/11 05:15, 5年前 , 11F
推F大
01/11 05:15, 11F
‣ 更多 AAQ8 的文章
文章代碼(AID): #1SDl6VlP (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 4 之 5 篇)：
排序： 最舊先 | 最新先 | 留言數
理工
2
4
[理工] 資結題庫 資結題庫
AAQ8
5年前, 12/19
理工
2
6
[理工] 資結題庫 資結題庫
AAQ8
5年前, 01/02
理工
3
11
[理工] 資結題庫 資結題庫
AAQ8
5年前, 01/10
在新視窗開啟完整討論串 (共5篇)
‣ 更多 AAQ8 的文章
文章代碼(AID): #1SDl6VlP (Grad-ProbAsk)