各位大大好 小弟有个问题想请教
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
跟讲义不一样,哪个才对?
感谢
作者:
skyHuan (Huan)
2018-10-06 22:00:00这题洪逸的DS笔记有类似的想法,在sort那章的最后面,同意楼上说的2*a_n-1分别找出两群的min跟Max,两群的min跟Max再分别做比较才知道谁是真正的min跟Max,所以+2
作者:
eggy1018 (羅密æèˆ‡è±¬éŽå¤œ)
2018-10-06 21:01:00个人觉得应该是an找n个中最大值的比较次数相当于找n-1个中最大值(an-1)找完之后再比一次所以加一因为要同时找最大&最小所以整体*2题外话,比an-1次不代表一定是极值,因为是在n个里面找,所以你的方式我觉得可能有些瑕疵,如果有错误还请指正
作者: nannnnn (nannnnn) 2018-10-06 19:48:00
因为要同时找出最大和最小?所以子问题两群中小的跟小的比,大的再跟大的比,这样就比较两次了
喔喔 好像是耶同意n大&s大 感谢指点!!谢谢e大关于极值的指正,讲"该群极值"也许比较清楚仔细想想发现同时找极大极小不需要全部系数乘 2因为 a_n-1 包含了在 2^n-1 个数中找极大与找极小的总次数