PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] quicksort on peaked array

看板Prob_Solve (計算數學 Problem Solving)作者 (又跳禎)時間10年前 (2014/11/02 14:35), 10年前編輯推噓0(0推 0噓 12→)
留言12則, 1人參與, 最新討論串1/1
題目:令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
→
11/02 18:33, , 1F
問題： 1,2,3,4,5 算 peaked array 嗎
11/02 18:33, 1F
若照這題題意的話應該是不算 ※ 編輯: jb679123 (140.123.214.127), 11/02/2014 22:47:34
→
11/03 11:31, , 2F
最糟看起來是沒錯，但是最佳有點 undefined 的味道
11/03 11:31, 2F
→
11/03 11:32, , 3F
因為 T(n) 是用 qs 排序 peak array 的時間，但是 pivot
11/03 11:32, 3F
→
11/03 11:33, , 4F
的選擇會影響到 split 的結果是不是兩個 peak array
11/03 11:33, 4F
→
11/03 11:34, , 5F
其次，{ 2, 3} 這狀況照定義不是 peak array ，所以沒法用
11/03 11:34, 5F
→
11/03 11:35, , 6F
T(n) 來表示
11/03 11:35, 6F
→
11/03 11:40, , 7F
不過照這樣講起來， worst case 也會碰到這種狀況，所以
11/03 11:40, 7F
→
11/03 11:40, , 8F
也沒辦法用 T(n) 來表示
11/03 11:40, 8F
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
→
11/03 12:51, , 9F
所以說有點 undefined 的味道，因為 T(k) 是用 qs 排 peak arr
11/03 12:51, 9F
→
11/03 12:52, , 10F
的時間，除非 split 的時候 n -> [a, b] 兩個 a 跟 b 都是
11/03 12:52, 10F
→
11/03 12:53, , 11F
peaked array ，不然是沒辦法用 T(a)+T(b) 來表示，這樣就回到
11/03 12:53, 11F
→
11/03 12:53, , 12F
原始 qs 了。
11/03 12:53, 12F
‣ 更多 jb679123 的文章
文章代碼(AID): #1KLT31jg (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 jb679123 的文章
文章代碼(AID): #1KLT31jg (Prob_Solve)