找出具有n个元素的集合中最大的两个元素，要求比较次数尽可能少（三种算法的思考）

转http://blog.csdn.net/will_lee_buaa/article/details/12884989

题目：给定具有n个元素的集合，找出最大的两个元素，算法要求比较次数尽可能少

 

这个题目要做出来很简单，但是要找出比较次数尽可能少的算法也不是件容易的事情。

对于这个题目，目前有三种方法比较流行。

第一种：对集合扫描两遍（当然也可以扫描一遍，同时最大和第二大元素，但花费的比较次数和扫描两遍，在最坏情况下是一样的），第一遍找出最大的元素，第二遍从剩余的元素中找出最大的元素，即整个集合的第二大元素。两遍扫描需要的比较次数为2*n-3次

 

第二种：将集合每两个元素一组，分成n/2组，组内两个元素先进行比较，初始化两个元素，max1,max2,代表当前最大和第二大元素，然后从第一组开始，让max1和max2,依次和每组进行比较，并更新max1和max2,得到最终的整个集合的max1和max2。整个过程需要的比较次数为3*n/2次

 

第三种：此种方案，似乎被几乎所有人认为是最好的方案，可是事实却是相反的！下面进行第三种方案的分析：

第一步：将集合每两个元素一组，分成n/2组，组内元素进行比较，选出比较大的那个元素。

第二步：将第一步选出的n/2个元素递归使用第一步的处理方式。直到选出集合中最大的元素。

第三步：从和最大元素比较过的元素中，选出最大的元素即为第二大元素。

从第三步可以看出，我们需要开辟一块空间，在每一步中记录和每一个元素比较过的元素集合。因为，在第二部执行结束之前，我们并不知道最大元素是哪个元素。从第一步和第二步我们可以想象出来，整个比较过程像一棵二叉树，先从n个子节点开始，一层一层比较，一直到根节点（最大元素）。两个子节点的父节点是两个子节点中较大的那个元素。因此我们可以得到和最大元素比较过的元素的个数等于树的高度，即lgn，所以第三步需要的比较次数为lgn-1,而第一步和第二步需要的比较次数为n-1次，所以总的比较次数为n+lgn-2次，似乎比第一种和第二种方案要好些。

但是，第三种方案需要一块内存空间记录和每一个元素比较过的元素，这个内存空间用数组表示是个二维数组（可以用链表等其他数据结构表示，不影响后面的分析结果），A[1..n][1..lgn],由于n是要处理元素的规模，因此，二位数组需要动态申请，并初始化，这需要花费nlgn的时间！！从这里就可以看出来，第三种方案属于捡了芝麻，丢了西瓜！因此，此种方案是不可取的。

我们可以尝试着对第三种方案进行优化，能不能把A[1..n][1..lgn]二维数组优化为一维数组。

我们可以在算法最开始的时候对集合扫描一遍，找到最大元素，这个时候，我们只需要一个大小为lgn的一维数组来记录和最大元素比较过的元素了，但是对集合扫描一遍需要n-1次比较，所以优化后的总的比较次数为2*n+lgn-3次，还是比前两种方案要差！！

 

注：在我们专注于比较次数的时候，忽略了赋值操作，在三种算法中赋值操作的次数不比比较次数要少，但是因为三种算法的赋值操作次数差不多，上面的分析方法就忽略了赋值操作的影响。