本文主要是介绍算法导论 9.1-1 求第二小元素 (这篇文章写的很好转来学习),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
原文链接:http://blog.csdn.net/mishifangxiangdefeng
一、题目
证明:在最坏情况下,利用n+ceil(lgn)-2次比较,即可得到n个元素中的第2小元素。(提示:同时找最小元素)
二、算法过程
step1:对所有元素,两个一组比较大小,小的一个进入下一轮比较。一直到比较出最小的元素。此时所有比较结果构成一棵二叉树。比较次数为n-1。
step2:沿着树从树根向下到叶子,找出第二小的元素,比较次数是ceil[lgn]-1。令m2[p]表示以p为根的树中的第二小元素。对于当前处理结点为p,key[p] = min{key[left[p]], key[right[p]]}。假设key[p] = key[left[p]],则m2[p] = min{m2[left[p]], key[right[p]]}
三、思考过程
1.根据提示,需要同时找最小元素,找最小元素的比较次数至少为n-1
2.在找次小元素时,尽量使用step1所产生的附加信息
3.次小值一定是在step1中与最小元素直接比较的过程中被淘汰的那些数
4.若“step1中与最小元素直接比较的过程中被淘汰的数”的个数为m,找次小值的比较次数为m-1
5.常规方法中,最坏情况下,m = n-1
6.调整算法,使最坏情况下m = ceil[lgn]
7.最终算法比较次数 = (n-1) + (m-1) = n + ceil[lgn] - 2
四、详细证明
1.找最小元素的比较次数至少为n-1
把每个元素看作是一个集合,这个集合有一个特殊的属性,即集合内的最小值。
初始状态下,每个元素是一个值,集合的最小值就是这个元素的值。
两个元素比较的过程,可以看作是两个元素分别所在的集合的merge过程,同时更新的集合的最小值属性。
最后剩下一个集合时该集合的最小值就是整个数组的最小值。
一定是两个在不同集合的元素之间才会发生比较,处于同一集合的元素是不需要比较的。
n个集合至少要经过n-1次merge才能成为一个集合。
2.次小值一定是在step1中与最小元素直接比较的过程中被淘汰的那些数
参与比较的值,一定是集合中最小的值。
没有参与比较的值,有两种情况:
(1)若这个集合的最小值不是整个数组的最小值
那么这个值一定不是次小值,因此不用考虑
(2)若这个集合的最小值是整个数组的最小值,za
那么这个值有可能是次小值,但它也一定是在更早的某个比较过程中合并进来的,因此继续向前追溯。
3.常规方法中,最坏情况下,m = n-1
这个的常规方法是指
用如图来表示这种算法产生最小值的比较过程。
4.调整算法,使最坏情况下m = ceil[lgn]
把上图转换为这样,可知m与叶子结点的深度有关,最坏情况下的m就是树的叶子结点的最大深度,也就是二叉树的高度。
把二叉树调整为完全二叉树,树的高度就是ceil[lgn]了
----->
五、代码说明
1.虽然推导过程使用了二叉树,但是在实际算法实现过程中使用的是数组(有点类似第六章堆的实现),以简化算法。
用数组的下标代替结点的地址,用数组下标的索引代替指针。
2.指针nextTarget:每一次比较后,有可能是最小元素的侯选值链表,以数组元素0为head,通过nextTarget串联起来
指针nextSecond:假设数组元素a是最小元素,记录每次与a直接比较过的元素,也就是a对应的次小值候选者链表,以a为head,通过nextSecond串联起来
3.比较过程做了封装,用于统计比较次数。
4.初始情况下,每个元素都在nextTarget链表中,每比较一次,nextTarget链接中少一个元素。
当nextTarget链表中只剩下一个元素时,选择以这个元素为head的nextSecond链表中的最大值,就是整个数组的次小值。
5.假设数据有个5元素,依次为1,2,3,4,5,主要过程如图:
实心箭头表示nextTarget
空心箭头表示nextSecond
这篇关于算法导论 9.1-1 求第二小元素 (这篇文章写的很好转来学习)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!