作者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/cn.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