算法导论 9.1-1 求第二小元素

# 一、题目描述 证明：在最坏情况下，利用n+ceil(lgn)-2次比较，即可得到n个元素中的第2小元素。（提示：同时找最小元素） # 二、常规方法 使用两次for循环，分别将数组从前往后扫描。 第一扫次扫描过程中，不断记录和更新当前情况下的最小元素。 第二次和扫描过程中，不断记录和更新当前情况下的第二小元素。 伪代码如下： ~~~ Int min = array[0], minId = 0; FOR i in [1, n), i++ DO IF (array[i] < min) DO Min = array[i]; minId = i; DONE DONE Int secId = ( minId = 0 ? 1 : 0 ), sec = array[secId]; FOR i in [secId+1, n), i++ DO IF (i = minId) CONTINUE IF ( array[i] < sec ) DO Sec = array[i]; secId = i; DONE DONE ~~~ # 三、常规方法的比较次数 第一个循环过程中，每次循环内部的比较次数为1次，循环次数即扫描的元素个数为n-1，因此比较第一次循环过程的次数是n-1。 第二个循环过程中，每次循环内部的比较次数也中1次，循环次数即扫描的元素个数为n-2（去去掉了最小元素），因此比较第二次循环过程的次数是n-2。 常规方法的比较次数为(n-1)+(n-2)，即2n-3次。 # 四、方法改进一 在第一次循环求最小元素的过程时，对元素内容一无所知，因此n-1次的比较是必要的，难有优化空间。 在第二次循环求第二小元素的过程时，对元素的内容不再是一无所知。如果充分利用第一次循环所得到的信息，也许可以省掉第二次循环中不必要的比较。 本次优化的重点在第二次循环。 # 五、第一次循环的可用信息 原理： 如果 a > b 且 b > c，那么不需要经过a和c的比较就可以知道 a > c。 信息1： 假设数组中的元素为a, b, c, d, e, f, g … 。 当扫描到元素d时，最小元素为c，可知 a > c, b > c, d > c。 当扫描到元素e时，最小元素变为了e，可知 e > c。 那么 a > c > e, b > c > e, d > c > e， a,b,d不可能是第二小元素或最小元素 c是第二小元素，e是最小元素 信息2： 接着上文继续扫描，当扫描到元素e时，最小元素为e，结论如上。 当扫描到元素g时，最小元素仍为e，可知f > e, g > e。 那么a > c > e, b > c > e, d > c > e, f > e, g > e a, b, d不可能是第二小元素或最小元素 c, f, g有可能是第二小元素，e是最小元素 # 六、根据第一遍的可用信息作第二次循环 假设已经作过第一次扫描，找到了最小元素，为e，现在要充分利用第一次扫描的信息作第二次扫描。 这一次，我们并不是对除了e以外的所有元素扫描，而是只选择其中一部分。选择的依据来自于上一节的内容。 我们大胆猜测，第二小元素的候选值是那些在第一次扫描过程中与e做过直接比较的元素。 证明如下： 1. 在第一次循环的过程中，第二小元素一定与最后元素e直接比较过。 证明： 第一种情况，在数组顺序中，第二小元素在e之前出现 在出现之前，第二小元素一直都是被当作当前状态的最小元素，遇到e之后，因为与e比较失败，最小元素才变成了e。 第二种情况，在数组顺序中，第二小元素在e之后出现 e会与后面的每一个元素直接比较。 2. 没有与最小元素e直接比较过的元素一定不会是第二小元素 证明过程与1相反，略。 # 七、方法改进一的伪代码 第一次扫描的比较没有改变，只是每次比较的过程记录下来，以便第二次扫描的时候知道某个元素曾经和谁做过比较。 ~~~ Int min = array[0], minId = 0; FOR i in [1, n), i++ DO IF (array[i] < min) DO Min = array[i]; minId = i; QUEUE[i].PUSH(min); ELSE QUEUE[minId].push(array[i]); DONE DONE ~~~ 第二次扫描时，仅取出最小元素所对应的队列元素做比较 ~~~ Int secId = QUEUE[minId].ELEMET(0) FOR i in [1, QUEUE[minId].size), i++ DO IF (QUEUE[minId].ELEMET(i) < sec ) DO Sec = QUEUE[minId].ELEMET(i); DONE DONE ~~~ # 八、方法改进一的比较次数 第一次扫描的次数仍然为n-1，主要差别在于第二次扫描。 第二次扫描也是FOR循环，每次循环内部的比较次数是1次，总的比较次数取决于 队列中元素的个数。假设个数为m，那么比较次数为m-1。 为了计算m，我画了这样一个图。叶子结点为数组中的元素。没有标字母的节点表示其它两个孩子结点的比较结果。画出这样的图，任假设一个结点为最小元素，都能很清晰地看出其队列中元素的个数。  我们取两种最极端的情况： 假如最小元素为A，那么其队列中的元素为B, C, D，3个元素 假如最小元素为D，那么其队列中的元素为A, B, C中的最小值，1个元素。 结论，方法改进一的比较次数最多为2n-3，最少为n-1，取决于最小元素所在位置。 # 九、方法改进二 虽然方法改进一相比于常规方法是有了改善，但最多比较次数仍然需要2n-3次，未达到题目所要求。这次我们方找最小元素的过程入手。 上文已经说过，求最元素的过程到少要经过n-1次比较，这一点是难以改变的。但我们仍可以通过调整第一次遍历方式，使留给第二次遍历更多有用的信息。尽量让每个元素与其它元素的比较次数平均化，这样，当任意一个元素成为最小元素时，它的队列的元素个数都不会太多。仍然以上文的图为例：  方法改进一的第一次遍历可以画成这一样的图，数组中的每一元素是这个二叉树的叶子结点。假如某一个元素是最小元素，那么它的队列的元素即该叶子结点的高度。只要将树平均化，如下图所示，保证每一个叶子的高度都不会太高，那么每个元素对应的队列都就不会太大。  # 十、方法改进二的比较次数 方法改进二的伪代码比较复杂，请大家直接阅读源代码。 对于第一次遍历，比较次数仍为n-1。 对于第二次遍历，比较次数取决于第一次遍历转化生成的二叉树的高度h。 将二叉树平均化以后，树的高度为h= ceil[lgn]。 结论，方法改进二的比较次数最多为n+ ceil[lgn]-2。 # 十一、代码 产品代码 [https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter9/Exercise9_1_1.cpp](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter9/Exercise9_1_1.cpp) 测试代码 [https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/tst/chapter9/Exercise9_1_1Test.cpp](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/tst/chapter9/Exercise9_1_1Test.cpp)