作者jb679123 (又跳禎)
看板Prob_Solve
標題[問題] quicksort on peaked array
時間Sun Nov 2 14:35:40 2014
題目:令T(n)為使用quicksort排序一個peak陣列中n個元素的時間
peak array是指陣列中的元素大小像一個凸峰
ex:1,3,5,7,9,8,6,4,2
假設要排序上面的元素，那T(n)的遞迴是該怎麼寫??
目前知道最佳的情況是T(n)=2T(n)+c.n
最糟的情況是T(n)=T(n-1)+c.n
但像這種情況不知道該怎麼下手..
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.243.153.164
※ 文章網址: http://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1414910145.A.B6A.html
1F：→ yr: 問題： 1,2,3,4,5 算 peaked array 嗎 11/02 18:33
若照這題題意的話應該是不算
※ 編輯: jb679123 (140.123.214.127), 11/02/2014 22:47:34
2F：→ yr: 最糟看起來是沒錯，但是最佳有點 undefined 的味道 11/03 11:31
3F：→ yr: 因為 T(n) 是用 qs 排序 peak array 的時間，但是 pivot 11/03 11:32
4F：→ yr: 的選擇會影響到 split 的結果是不是兩個 peak array 11/03 11:33
5F：→ yr: 其次，{ 2, 3} 這狀況照定義不是 peak array ，所以沒法用 11/03 11:34
6F：→ yr: T(n) 來表示 11/03 11:35
7F：→ yr: 不過照這樣講起來， worst case 也會碰到這種狀況，所以 11/03 11:40
8F：→ yr: 也沒辦法用 T(n) 來表示 11/03 11:40
Y大好像誤解我的意思了XDD
我的最佳和最糟是指說元素在陣列中出現的情況
最糟就是元素是以遞增或遞減出現陣列中 EX:1,2,3,4,5 5,4,3,2,1
最佳則是每個PIVOT剛好可以把陣列分成兩等分
但這題是說陣列中的元素是以peak的方式出現 ex:1,3,5,7,9,8,6,4,2
就不是最佳或最糟的情況
所以不知道要怎麼下手...
※ 編輯: jb679123 (140.123.103.109), 11/03/2014 12:16:18
9F：→ yr: 所以說有點 undefined 的味道，因為 T(k) 是用 qs 排 peak arr 11/03 12:51
10F：→ yr: 的時間，除非 split 的時候 n -> [a, b] 兩個 a 跟 b 都是 11/03 12:52
11F：→ yr: peaked array ，不然是沒辦法用 T(a)+T(b) 來表示，這樣就回到 11/03 12:53
12F：→ yr: 原始 qs 了。 11/03 12:53