凭直觉判断,显然寻找第2小元素至少可以在 n-1+(n-1-1)=2 次比较后完成:先花 n-1 次比较寻找最小值,然后在剩余的 n-1 个元素中再用(n-1-1)次比较寻找到当前的最小值,就得到了第2小元素. 但这显然不是最优的解法.
实际上第i小问题用基于一种类似于快速排序的分区思想后可以平均在线性时间内解决,但其最坏情况运行时间为 O(n^2) ,而且常数因子也不好控制,所于这种算法对于仅仅需要找到第2小元素的本题来说,关系不大.
算法导论习题 9.1-1:证明:在最坏情况下,得用 n+lg(n)-2 次比较,即可找到 n 个元素中的第2小元素.
分析: 看见题目中有lg(n) 项,首先应该想到的是分治法,算法的思路如下:(为简单起见,不考虑取整的问题)
将 n 个元素分成 n/2 对.每一对之间互相比较.这样一共比较了 n/2 次.然后将每一对的较小元素放在 S[1...n/2] 数组中,较大的元素对应的放在 B[1...n/2]中.显然最小的元素肯定在数组S中,那么第2小的元素(设代号为X) 是否也在 S 中呢?
首先,假设第2小元素X在数组S 中,因为最小的元素也在数组S中,所以X在S中同样也肯定是第2小元素.这样我们可以递归的在S中继续寻找第2小元素,并将搜索的范围缩小了一半.
如果第2小元素X不在数组S中,(即在数组B中),由上面的分区算法知,在B中的元素必然大于相应位置上S中的元素.在这里X是第2小元素,它仅大于最小元素.所以它在B中的位置与最小元素在S中的位置相同.
综上可知:第2小元素X要么是S中的第2小元素,要么是B中位置与最小元素在S中的位置相同的元素.
这样算法就很明了了: 将 n 个元素分成 n/2 对比较,较大者放入B,较小者放入S,若B和S的大小为1,则B[1]作为第2小元素返回,S[1]作为最小元素返回(主要是想得到最小元素在S中的位置),若B和S的大小大于1,则递归的在S中寻找最小元素和第2小元素,并将S中得到的第2小元素与B中位置与最小元素在S中的位置相同的元素相比较(有点拗口),其中较小者便是真正的第2小元素.
举个例子吧,如: 在序列 3,2,5,8,6,4,9,7 中寻找第2小元素.
过程:首先分在[3,2] [5,8] [6,4] [9,7] 四组,经比较后得到 S1=2,5,4,7 B1=3,8,9,7.
再将 S1分区,得到 S2=2,4 B2=5,7 .
S2中最小值是2,第2小元素是4. B2中与S2中最小值对应的是5,因4小于5.所以得到S1的最小值是2,第2小元素是4, 在B1中与S1中最小值2对应的是3,因4>3,所以得到 整个序列的第2小元素为 3.完成.
算法分析: T(n)=n/2+T(n/2)+1 //其中的n/2是分区时比较的次数,1 是递归时S中得到的第2小元素与B中位置与最小元素在S中的位置相同的元素相比较的消耗.
T(2)=1.
解递归式即可:T(n)=n+lg(n)-2 .