[理工] in place的定義

看板Grad-ProbAsk作者 (野格炸彈)時間4年前 (2020/01/27 11:39), 編輯推噓1(1推 0噓 5→)
留言6則, 3人參與, 4年前最新討論串1/1
之前我查到的定義是只使用O(1)額外空間 那這樣的話quick sort在call遞迴的時候 長出的stack就不只O(1)了 那應該不是in place 可是stackoverflow上面有人說 因為quick sort只會在自己的array上做比較跟修改 所以是in place in place演算法的定義應該是什麼R ----- Sent from JPTT on my Sony H9493. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.8.221 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1580096358.A.4EB.html
→
01/27 11:54, 4年前 , 1F
quick sort也可以不用recursive的方式做 所以我覺得
01/27 11:54, 1F
→
01/27 11:54, 4年前 , 2F
應該算是in place
01/27 11:54, 2F
推
01/27 12:14, 4年前 , 3F
不用 recursion 做的 quick sort 大部分都需要 stack
01/27 12:14, 3F
→
01/27 12:25, 4年前 , 4F
sorting in place指的應該跟額外的memory space無關，
01/27 12:25, 4F
→
01/27 12:25, 4年前 , 5F
洪上課是說in place指的是在本身的array上操作，除了M
01/27 12:25, 5F
→
01/27 12:25, 4年前 , 6F
erge跟linear time的方法不是，其他都是in place
01/27 12:25, 6F
‣ 更多 misaka0120 的文章
文章代碼(AID): #1UBbjcJh (Grad-ProbAsk)