作者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/cn.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