[理工] in place的定義

[misaka0120 (野格炸彈)]

之前我查到的定義是只使用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
→ cossetannie: quick sort也可以不用recursive的方式做 所以我覺得
→ cossetannie: 應該算是in place
推 FRAXIS: 不用 recursion 做的 quick sort 大部分都需要 stack
→ gcobc19622: sorting in place指的應該跟額外的memory space無關，
→ gcobc19622: 洪上課是說in place指的是在本身的array上操作，除了M
→ gcobc19622: erge跟linear time的方法不是，其他都是in place