PTT
Submit
Submit
選擇語言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] 資結題庫
作者:
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
繼續閱讀
[理工] 107交大…一堆問題!
Aa841018
[理工] [線代] 實數矩陣特徵向量問題
leekevinming
104中正離散
marks1592
[理工] 計組乘法
lionlin
[理工] 交大107 多題計組討論
zaq851017
[理工] 104 交大 計系 4
dumpling1234
[理工] 向量空間
aleswell
[理工] 中央103離散
o5739201
[理工] 邏輯電路的題目
lionlin
107 清大 計科 HPHC轉換
neutral9913
Links
booklink
Contact Us: admin [ a t ] ucptt.com