这一讲介绍选第二大的问题。
选第二大呢，它的输入是n个数的一个数组。
从这里边找出第二大的数，就是说从大到小来排列排在
第二的那个数。下边我们看一下一个顺序比较的算法。
这是一个比较简单的方法。顺序比较呢，我们先找到数组里的最大数。
这个在上一讲找最大中，已经给出了一个顺序比较的算法， 怎么样来找最大，然后从剩下的n减1个数
把这个最大拿掉，剩下的n减1个数我们再找一次最大。
那这个最大就是整个数组的第二大，那这个算法的工作量是多少呢？
根据找最大算法的工作量分析，它第一次找整个数组的最大的时候
需要做n减1次的比较，那么第二步呢在n减1个数中，再找最大
它需要做的比较次数正好是n减2次，那这两个合到一起呢，是2n减3次
的比较，这是顺序比较的算法，它需要2n减3次的比较次数。
下面我们考虑一下提高效率的一个途径，怎么样来提高算法的效率呢？
先分析一下一个数能作为第二大数 的条件，如果一个数是整个数组的第二大数
它仅仅在与最大数的比较中被淘汰，如果 它不是被最大所淘汰，而是被其他的数淘汰以后。
那它至少也是在第三大以后的数了，不会成为第二大，所以只有被最大的数
所淘汰的数中，才有资格成为第二大。因此我们在确定第二大数的时候，
必须知道了最大数，而且是被它淘汰才能成为第二大。
下边我们看看改进的途径是什么呢，就是在确定
最大数的过程中，记录下来被最大数直接淘汰的元素。
那我们在找第二大的时候，就在这个范围里 来找就行了，就是说被最大数直接淘汰的那些数中，
它里边来找最大那就是第二大数，这就是它提高效率的途径。我们不是在
所有的数中来找第二大，而是在被最大所淘汰的 范围里来找，这个范围就缩小了。那这里边，
它代价是什么呢，就是我们要做记录，这个记录呢实际上是要需要空间的，
这是一个用空间来换时间的策略。下边我们看一下算法的实现，
这就是锦标赛的算法。这个算法怎么做呢，先两两分组比较，
把大的我们认为是胜利的进入下一轮，那么比较小的那个数就被
淘汰掉，所以两个元素一组，每组中经过一次比较会淘汰掉一个数。
然后剩下的数，淘汰以后剩下的
数呢，就进入下一轮，下一轮再两两分组，每组再进行比较，再淘汰。
直到最后剩下一个元素，也就是冠军，把它剩下为止。
啊，这是第一步的过程。那么在每次比较中，两个元素比较会淘汰掉
较小的元素，淘汰的时候就把这个被淘汰的元素记录在淘汰它的那个元素的链表上。
所以每做一次比较呢就会做一个记录，这是在比较中的操作。
那么最后当这个最大的元素产生以后，就检查它的链表。这个
链表是被它直接淘汰的元素都记在这个链表里边，然后在这个链表里边
找到最大的元素，就是整个数组的第二大。下边我们看一下这个伪码。
这个伪码呢它就是刚才的这个过程。这个k初始是等于n，
就是参与淘汰的元素数。然后把这个k个元素两两分组。
分成2分之k下去整个组，每个组的两个数进行比较，找到比较大的数。
那第四步就是我们所增加的这个操作， 把这个被淘汰的数记录到较大的数的链表里边去。
然后，这样一轮淘汰完了以后，如果k是个奇数，
就是每个组剩一个数嘛，这是进入下一轮的，如果它是个奇数的话，
那就把这个k的值，就是原始的这个k的值就除以2
再加1，就是淘汰以后剩下的元素数。
啊，如果它是个偶数的话，就直接
下取整就可以了。那么当这个k是淘汰以后
得胜的那些个数准备进入下一轮的数的个数，如果它要是大于1的话，我们就接着
回到2，再分组进行淘汰，直到k等于1开始，这个时候就找到了最大的数。
然后把最大数的链表里边再找一次最大就是第二大。
这是整个的这个过程，我们看到这里边的 这几行1 2 3 4，是进行一轮淘汰的操作。
那么这个条件是继续分组，
进行下一轮淘汰的条件，当k等1的话这个条件就不成立了。
下边我们看一个实例，这是原始的数组。
然后我们进行分组，两个一组两个一组，这样分成了四个组，每个组
进行比较，比较以后，5比3大，5把3淘汰了，把3就记在5的链表上了。
那么第二组呢，6被淘汰了，6记在 7的链表上，第三组1记在2的链表上，
第四组，4被淘汰了，记在8的链表上。那么这四个元素
5、7、2、8是进入下一轮的元素。
这就是进入下一轮了，然后这一轮再继续分组， 分成两个组，然后这两个组再比较，比较以后，
把得胜的那个元素它的链表上再增加上 比较小的元素作为它链表的元素，那么
7原来是有一个6，然后在7跟5比较的时候，5又 被淘汰了，记在7的链表后面，这个时候7后边就
淘汰了两个数了。同样的8，8淘汰了4已经记在它的 链表里面了，8和2再比较呢，2又被淘汰了，
又记在8的链表里面，这是第二轮分组的结果。
那么这个时候只有8和7两个数剩下来了，那这个就进入
第三轮，它们再接着分组，那只有一个组了。这个淘汰过去以后呢，
7被8淘汰了，7又记入了8的链表，那么8就是最后得到的最大数。
在此刻，当它只剩它一个数的时候，它的链表已经记了4 2 7三个数。
那第二步呢就得在这三个数的范围里头找最大，就是7。
7得到的就是整个数组的第二大。
下边我们看一下它的时间分析，为了做时间分析，需要有这样一个命题。
参与比较的元素有t个元素，经过i轮淘汰以后，元素的个数
至多是t除以2的i次方，上取整，是这样一个值。
那这个值的证明呢，我们可以通过对i归纳来做。
当i等于1的时候，就是经过一轮的淘汰。经过一轮的淘汰，我们小组的个数是2分之t
下取整，那么每个组淘汰一个元素呢会淘汰掉2分之t 下取整个元素，那进入下一轮的元素数是什么呢？
用元素总数减掉淘汰的元素数，就是进入下一轮的元素数。
那这个刚好满足i等于1的时候，这两个值是 一样的，所以当i等于1的时候这个命题是对的。
下面假设i轮分组以后，淘汰的元素数至多
是t除以2的i次方上取整。就是说这个命题
对于i来讲是正确的，那么我们考虑再进行一轮淘汰在i加1轮淘汰
以后，元素数应该等于这个值除以2再上取整，也就是这个公式。
那这个公式呢，原来我们讲过的数学基础，两次取整可以把这个取整号去掉，去掉以后呢，
它化简成，t除以2的i加1次方上取整。
那就说明对i加1来讲，这个公式也是对的。
这是我们看到的第一个命题，利用这个命题呢来进行
时间复杂度的分析。下面我们看看第二个结果，就是说
这个最大这个数，在第一阶段分组比赛中总共进行了 log
n上取整次比较，也就意味着被最大数所淘汰的元素个数
就是这个log n上取整。下边我们看看这个命题，假设
到产生最大数的时候总计进行了k轮的淘汰，根据命题1
这个淘汰的次数刚好是n除以2的k次方上取整。
那么经过k轮淘汰到产生最大的时候，元素只有一个元素了，所以经过
k轮淘汰以后呢，元素个数等于1，我们就得到了第一个等式。
根据这个等式呢，我们来讨论一下，当n正好 是2的幂的时候，那么n正好是2的幂。
也就是n等于2的d次方，而根据这个公式，n除以2的k次方上取整等于1。
可以知道，这个k和d完全是相等的数，那么d呢正好是log n， k也就是等于log n，log
n跟log n上取整是一样，因为n正好是2的幂，这就是
满足了我们所讲的这个条件。那么我们看到当n不是2的幂，
它是处在2的d次方和2的d加1次方之间的这样一个数，
它不正好是2的幂。那么当它除以2的k次方上取整，
根据这个结果我们代进去，那么这个时候这个k的值正好是等于d加1。
就是它只有经过d加1次的淘汰以后才能得到整数1，那么d加1等于多少呢？ 正好是log
n的上取整，因为这个n是处在这个数跟这个数之间。
它要log上取整，正好等于d加1，这就是 得到的结果，和刚才它正好是2的幂的结果是一样的，
都满足这个公式。有了这个公式就清楚了，我们知道在找到最大以后，它要淘汰
掉多少个数呢，正是log n上取整个数，这是第二个命题的结果。
那下边就可以看到，整个算法需要进行多少次的比较呢？
可以计算一下，在第一阶段我们在产生最大的过程中，要淘汰掉n减1个元素，
它恰好比较了n减1次，因为每比一次正好淘汰一个元素， 这是它的工作量。那么在第二阶段，
在找第二大的过程中，它是在被最大所淘汰的元素范围中来找，而 被最大淘汰的元素是log
n的上取整，从这里边找最大就是整个数组的第二大， 需要淘汰掉log
n上取整减1个元素，而比较次数恰好是log n的上取整
减1，那么整个算法的工作量呢，就是这两部分加起来。
我们可以看到它总的比较次数应该满足下面的公式，就是把这
两项加起来就是下面这个公式，把它化简以后得到下面这个结果。
这是一个锦标赛算法它的时间复杂度。
那这个算法呢，将来可以证明它是所有的找第二大
算法里头，如果以元素比较做基本运算的话，这是一个最好的算法。
把第二大问题小结一下，它有一个蛮力的算法，就是调用
两次找最大，这需要2n减3次的比较。
锦标赛的算法，刚才已经说明了，它需要这么多次的比较。
看到这个算法比上一个算法时间复杂度要低，它主要
用的技术就是用空间换时间的技术，我们需要记录下来被最大所淘汰的数。
Wanling QuProfessor
