[理工] Quicksort差別

看板Grad-ProbAsk作者 (Luan)時間7年前 (2017/01/15 17:56), 編輯推噓3(3推 0噓 25→)
留言28則, 8人參與, 最新討論串1/1
想問 一般的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
推
01/15 18:23, , 1F
Worst應該n^2
01/15 18:23, 1F
→
01/15 18:24, , 2F
Best nlogn
01/15 18:24, 2F
→
01/15 18:24, , 3F
我覺得啦
01/15 18:24, 3F
推
01/15 18:30, , 4F
Worst 好像也是nlogn才對
01/15 18:30, 4F
→
01/15 18:30, , 5F
不確定 懇求神人幫解答了
01/15 18:30, 5F
推
01/15 18:41, , 6F
Randomized的話就不會有分 worst, best了呦
01/15 18:41, 6F
→
01/15 18:42, , 7F
因為原型之所以會分Best, worst 是因為pivot可能因
01/15 18:42, 7F
→
01/15 18:42, , 8F
輸入資料的形式而有所差異 randomized就沒這問題
01/15 18:42, 8F
→
01/15 18:44, , 9F
Randomized 並不算是一般Qucick sort average的情況
01/15 18:44, 9F
→
01/15 18:44, , 10F
你再去翻書 會發現兩個是不同證明
01/15 18:44, 10F
→
01/15 19:01, , 11F
randomized 只是在挑pivot的時候使用亂數，還是有可能出現w
01/15 19:01, 11F
→
01/15 19:01, , 12F
orst case = O(n^2)
01/15 19:01, 12F
→
01/15 19:48, , 13F
原來如此，我修正一下 那randomized的average的確是
01/15 19:48, 13F
→
01/15 19:48, , 14F
O(nlogn)
01/15 19:48, 14F
→
01/15 20:17, , 15F
好的 謝謝樓上各位大大！！！
01/15 20:17, 15F
→
01/15 20:59, , 16F
所以就是randomized的worst case還是O(n^2)，但是出現
01/15 20:59, 16F
→
01/15 20:59, , 17F
的機率比較低嗎？
01/15 20:59, 17F
→
01/15 21:06, , 18F
還是出現的機率其實要考慮的東西更多不能單純這樣問...
01/15 21:06, 18F
→
01/15 21:07, , 19F
randomized基本上不影響qsort的複雜度, 只是考慮輸入資
01/15 21:07, 19F
→
01/15 21:07, , 20F
料擁有的特性我們難以預測所以提供一個公正的方法選p
01/15 21:07, 20F
→
01/15 21:09, , 21F
就像老師要評斷班上同學好壞的時候要選一個標準
01/15 21:09, 21F
→
01/15 21:09, , 22F
了解了，謝謝
01/15 21:09, 22F
→
01/15 21:09, , 23F
跟我理解的差不多 pivot是隨機選的 沒甚麼差別@@
01/15 21:09, 23F
→
01/15 21:10, , 24F
如果每次都選1號 然後1號又是超級優等生 這樣評斷整班幾
01/15 21:10, 24F
→
01/15 21:11, , 25F
乎很爛是不公平的 所以隨機挑 但偶爾還是會挑到1號
01/15 21:11, 25F
→
01/15 21:15, , 26F
就是...沒差 跟原型一樣XD
01/15 21:15, 26F
→
01/15 22:33, , 27F
randomzed quicksort 證明的是 expected running time
01/15 22:33, 27F
→
01/15 22:33, , 28F
不是 average running time
01/15 22:33, 28F
‣ 更多 cyc4542015 的文章
文章代碼(AID): #1OUqTbq- (Grad-ProbAsk)