推 genius945:謝謝! 想請問一下F大你答案會怎麼寫,我寫得亂七八糟... 12/20 22:47
推 kiwidoit:推神人F大! 12/20 22:59
→ FRAXIS:其實只要兩層一起思考就好 每過兩層輸入大小就減半 12/21 08:21
→ FRAXIS:處理兩層的時間為O(n) 所以就得到T(n) = 2T(n/2) + O(n) 12/21 08:22
推 genius945:!! 太感謝了 整個被點醒 12/21 10:57
※ 引述《genius945 (添財)》之銘言：
: 4.
: 不太懂題目問什麼...
: 當考試寫我就瞎猜寫了避免worst case的辦法
: google也查不到 schizophrenic adversary 是啥...
: 是要寫middle of 3 或是middle of middle(忘了名字,大概就是切成很多等分這樣)?
: 謝謝
這是問說Quicksort執行的時候，如果Best Case和Worst Case交互出現，
也就是說，在第一層會挑到一個很好的pivot，使得輸入會剛好切半，
但是到下一層的時候就會挑到一個很差的pivot，使得輸入被切成1和n-1。
此時的時間複雜度會是多少，答案應該是O(nlgn)吧
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50