本文共 900 字，大约阅读时间需要 3 分钟。

算法导论中的一道习题：

证明： 在最坏情况下，找到n个元素中的第二小的元素需要n+ceil(lgn)-2次比较。（提示：可以同时找到最小元素，ceil表示向上取整）

思路：

找到最小元素需要n-1次比较。采用两两结合比较的方法。如果n为奇数，则取第一个元素为临时最小元素min，其它两两结合比较，形成一个类似树的比较过程。如果n为偶数，则直接进行两两结合比较，根节点即为最小元素。

接下来查找第二小元素，需要ceil(lgn)-1次比较。考虑：第二小元素一定和第一小元素进行了比较，所以可以直接在比较树的根节点到叶节点中的元素中去寻找，当n为2^n到2^(n+1)-1时，树高为ceil（lgn）, 需要比较次数ceil（lgn）-1(减去跟节点的那一层) 

举个例子：

0              /   \             1     0           /      /   \         1      2     0       /  \    /  \    / \      1   3  4  2  0 7

假设有一批数1，3,4,2,0,7 。有n个数，他所产生的比较树树高为ceil(lgn),在树高为ceil(lgn)的比较树中，最多有ceil(lgn)-1个与之比较过，根节点那层减去，故为ceil(lgn) -1.（这里感谢 @doodlesomething同学的解释～）

那么，我们发散一下思维，最坏情况下是上面的结果，那么最好情况下呢？

思路：

“设定两个存储单元：N1,N2，N1中保存最小的两个中较大的一个，N2中保存最小的一个。

 假设前两个数是最小的，比较这两个数，将小的放在N2中，大的放在N1中。  从第三个开始循环与N1比较，如果当前比较的值大于N1的值，则继续循环直到最后。如果当前比较的值小于N1的值，则与N2做比较，如果大于N2则用当前值替换N1的值，如果小于N2，则用N2的值替换N1的值，当前值替换N2的值。  这样做法应该是比较最少的了，最少比较：N-1次，最多比较：2N-3次。”

思路有限，如果你有好的想法，请指教！谢谢～

参考：

转载地址：http://rjmab.baihongyu.com/