[理工] 資結題庫

作者: AAQ8 (不要就是要)   2019-01-10 15:17:48
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
麻煩各位 謝謝
作者: kyrie77 (NTU KI)   2019-01-11 05:15:00
推F大
作者: FRAXIS (喔喔)   2019-01-10 22:55:00
Quicksort 算不算 inplace 取決於你 inplace 的定義如果你定義 inplace 是最多只能用 O(1) 額外空間,那quicksort 就不是 in-place不過因為 quicksort 有一種版本可以最多只使用O(lg n)空間 所以很多人也認為 quicksort 是 in-place理論上 quicksort 可以只使用 O(1) 空間,只是方法很複雜所以教科書上也不會提
作者: BroccolYee (花椰菜)   2019-01-10 17:09:00
只有4,5 1,2算swap 剩下都是兩個串列擺前後直接合併另外quick sort的空間複雜度是call遞迴stack的層數它依然是in-place

Links booklink

Contact Us: admin [ a t ] ucptt.com