為什麼這篇quicksort時間複雜度鄉民發文收入到精華區：因為在quicksort時間複雜度這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者cyc4542015 (Luan)看板Grad-ProbAsk標題[理工] Quicksort差...
想問
一般的QuickSort和Randomize的QuickSort 時間複雜度有差嗎
因為書上的Randomize是用機率算的 這樣是不是在算average的狀況？
那如果是問Worst case和Best case的話
該怎麼看呢？
謝謝大大解答QQ
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.116.1.136
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484474213.A.D3E.html
推 AllenPaul: Worst應該n^2 01/15 18:23
→ AllenPaul: Best nlogn 01/15 18:24
→ AllenPaul: 我覺得啦 01/15 18:24
推 AllenPaul: Worst 好像也是nlogn才對 01/15 18:30
→ AllenPaul: 不確定 懇求神人幫解答了 01/15 18:30
推 kyuudonut: Randomized的話就不會有分 worst, best了呦 01/15 18:41
→ kyuudonut: 因為原型之所以會分Best, worst 是因為pivot可能因 01/15 18:42
→ kyuudonut: 輸入資料的形式而有所差異 randomized就沒這問題 01/15 18:42
→ kyuudonut: Randomized 並不算是一般Qucick sort average的情況 01/15 18:44
→ kyuudonut: 你再去翻書 會發現兩個是不同證明 01/15 18:44
→ gouya: randomized 只是在挑pivot的時候使用亂數，還是有可能出現w 01/15 19:01
→ gouya: orst case = O(n^2) 01/15 19:01
→ kyuudonut: 原來如此，我修正一下 那randomized的average的確是 01/15 19:48
→ kyuudonut: O(nlogn) 01/15 19:48
→ cyc4542015: 好的 謝謝樓上各位大大！！！ 01/15 20:17
→ yupog2003: 所以就是randomized的worst case還是O(n^2)，但是出現 01/15 20:59
→ yupog2003: 的機率比較低嗎？ 01/15 20:59
→ yupog2003: 還是出現的機率其實要考慮的東西更多不能單純這樣問... 01/15 21:06
→ HEroKuma: randomized基本上不影響qsort的複雜度, 只是考慮輸入資 01/15 21:07
→ HEroKuma: 料擁有的特性我們難以預測所以提供一個公正的方法選p 01/15 21:07
→ HEroKuma: 就像老師要評斷班上同學好壞的時候要選一個標準 01/15 21:09
→ yupog2003: 了解了，謝謝 01/15 21:09
→ ken52011219: 跟我理解的差不多 pivot是隨機選的 沒甚麼差別@@ 01/15 21:09
→ HEroKuma: 如果每次都選1號 然後1號又是超級優等生 這樣評斷整班幾 01/15 21:10
→ HEroKuma: 乎很爛是不公平的 所以隨機挑 但偶爾還是會挑到1號 01/15 21:11
→ kyuudonut: 就是...沒差 跟原型一樣XD 01/15 21:15
→ FRAXIS: randomzed quicksort 證明的是 expected running time 01/15 22:33
→ FRAXIS: 不是 average running time 01/15 22:33