[理工] 資結

[bouwhat (微笑的故事)]

quick sort is the optimal sort of comparison based sort for different number.
(F)
請問為什麼不對？
average和best都是O(nlogn)符合comparison的定義，是不是問題出在optimal???

--
posted from android bbs reader on my samsung GT-I9003

https://market.android.com/details?id=com.bbs.reader

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 27.241.14.7
推 FRAXIS:QuickSort的Worst Case不好吧..
→ bouwhat:所以optimal sort是worse O(nlogn)嗎
推 numin:comparison based在worst case最快可達Ω(nlogn)，但quick
→ numin:sort在worst case是Θ(n^2)，所以False。另外optimal是merge
→ numin:sort和heap sort。
→ bouwhat:感謝!!!