[理工] 台大陳健輝離散講義Part1 p124

看板Grad-ProbAsk作者 (sillyboy)時間7年前 (2018/10/06 19:12), 編輯推噓4(4推 0噓 13→)
留言17則, 4人參與, 7年前最新討論串1/1
各位大大好 小弟有個問題想請教 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://www.ptt.cc/bbs/Grad-ProbAsk/M.1538824344.A.E22.html
推
10/06 19:48, 7年前 , 1F
因為要同時找出最大和最小？所以子問題兩群中小的跟小的
10/06 19:48, 1F
→
10/06 19:48, 7年前 , 2F
比，大的再跟大的比，這樣就比較兩次了
10/06 19:48, 2F
推
10/06 21:01, 7年前 , 3F
個人覺得應該是an找n個中最大值的比較次數相當於找n-1
10/06 21:01, 3F
→
10/06 21:01, 7年前 , 4F
個中最大值(an-1)找完之後再比一次所以加一
10/06 21:01, 4F
→
10/06 21:01, 7年前 , 5F
因為要同時找最大&最小所以整體*2
10/06 21:01, 5F
推
10/06 21:04, 7年前 , 6F
題外話，比an-1次不代表一定是極值，因為是在n個裡面找
10/06 21:04, 6F
→
10/06 21:04, 7年前 , 7F
，所以你的方式我覺得可能有些瑕疵，如果有錯誤還請指
10/06 21:04, 7F
→
10/06 21:04, 7年前 , 8F
正
10/06 21:04, 8F
推
10/06 22:00, 7年前 , 9F
這題洪逸的DS筆記有類似的想法，在sort那章的最後面，同
10/06 22:00, 9F
→
10/06 22:00, 7年前 , 10F
意樓上說的2*a_n-1分別找出兩群的min跟Max，兩群的min跟M
10/06 22:00, 10F
→
10/06 22:00, 7年前 , 11F
ax再分別做比較才知道誰是真正的min跟Max，所以+2
10/06 22:00, 11F
→
10/07 12:30, 7年前 , 12F
喔喔 好像是耶
10/07 12:30, 12F
→
10/07 12:30, 7年前 , 13F
同意n大&s大 感謝指點!!
10/07 12:30, 13F
→
10/07 12:30, 7年前 , 14F
謝謝e大關於極值的指正,講"該群極值"也許比較清楚
10/07 12:30, 14F
→
10/07 12:30, 7年前 , 15F
仔細想想發現同時找極大極小不需要全部係數乘 2
10/07 12:30, 15F
→
10/07 12:30, 7年前 , 16F
因為 a_n-1 包含了在 2^n-1 個數中找極大與找極小的總
10/07 12:30, 16F
→
10/07 12:30, 7年前 , 17F
次數
10/07 12:30, 17F
‣ 更多 love52697 的文章
文章代碼(AID): #1Rk9YOuY (Grad-ProbAsk)