[問題] quicksort on peaked array

[jb679123 (又跳禎)]

題目:令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://www.ptt.cc/bbs/Prob_Solve/M.1414910145.A.B6A.html
→ yr: 問題： 1,2,3,4,5 算 peaked array 嗎
若照這題題意的話應該是不算
※ 編輯: jb679123 (140.123.214.127), 11/02/2014 22:47:34
→ yr: 最糟看起來是沒錯，但是最佳有點 undefined 的味道
→ yr: 因為 T(n) 是用 qs 排序 peak array 的時間，但是 pivot
→ yr: 的選擇會影響到 split 的結果是不是兩個 peak array
→ yr: 其次，{ 2, 3} 這狀況照定義不是 peak array ，所以沒法用
→ yr: T(n) 來表示
→ yr: 不過照這樣講起來， worst case 也會碰到這種狀況，所以
→ yr: 也沒辦法用 T(n) 來表示
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
→ yr: 所以說有點 undefined 的味道，因為 T(k) 是用 qs 排 peak arr
→ yr: 的時間，除非 split 的時候 n -> [a, b] 兩個 a 跟 b 都是
→ yr: peaked array ，不然是沒辦法用 T(a)+T(b) 來表示，這樣就回到
→ yr: 原始 qs 了。