作者love52697 (sillyboy)
看板Grad-ProbAsk
標題[理工] 台大陳健輝離散講義Part1 p124
時間Sat Oct 6 19:12:21 2018
各位大大好 小弟有個問題想請教
https://i.imgur.com/A6e17EY.jpg
如圖，其中寫出原始Recurrence Relation的部分，為何 f(x) = 2 ?
就我的理解 f(x) = 1 才對，因為把 2^n 個數等分成兩群後，
各群的總比較數為 a_n-1，兩群各找出極值，總共做了 2 * a_n-1 次比較後，
剩兩個數，只需要再做一次比較即可找出極值，故 2^n 個數的總比較數 a_n ：
a_n = 2 * a_n-1 + 1
跟講義不一樣，哪個才對？
感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.170.147.183
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1538824344.A.E22.html
1F：推 nannnnn: 因為要同時找出最大和最小？所以子問題兩群中小的跟小的 10/06 19:48
2F：→ nannnnn: 比，大的再跟大的比，這樣就比較兩次了 10/06 19:48
3F：推 eggy1018: 個人覺得應該是an找n個中最大值的比較次數相當於找n-1 10/06 21:01
4F：→ eggy1018: 個中最大值(an-1)找完之後再比一次所以加一 10/06 21:01
5F：→ eggy1018: 因為要同時找最大&最小所以整體*2 10/06 21:01
6F：推 eggy1018: 題外話，比an-1次不代表一定是極值，因為是在n個裡面找 10/06 21:04
7F：→ eggy1018: ，所以你的方式我覺得可能有些瑕疵，如果有錯誤還請指 10/06 21:04
8F：→ eggy1018: 正 10/06 21:04
9F：推 skyHuan: 這題洪逸的DS筆記有類似的想法，在sort那章的最後面，同 10/06 22:00
10F：→ skyHuan: 意樓上說的2*a_n-1分別找出兩群的min跟Max，兩群的min跟M 10/06 22:00
11F：→ skyHuan: ax再分別做比較才知道誰是真正的min跟Max，所以+2 10/06 22:00
12F：→ love52697: 喔喔 好像是耶 10/07 12:30
13F：→ love52697: 同意n大&s大 感謝指點!! 10/07 12:30
14F：→ love52697: 謝謝e大關於極值的指正,講"該群極值"也許比較清楚 10/07 12:30
15F：→ love52697: 仔細想想發現同時找極大極小不需要全部係數乘 2 10/07 12:30
16F：→ love52697: 因為 a_n-1 包含了在 2^n-1 個數中找極大與找極小的總 10/07 12:30
17F：→ love52697: 次數 10/07 12:30