线性选择-最大值 中位数

---

1 Max & 对抗策略

我们常常需要在某个数据集合中，找出某个符合条件的元素，如最大值。对于找最大的值，从关键操作的角度来看，不难知道其下界为$n-1$n−1次比较，证明需要用到adversary argument，即构造一些具有挑战性的输入来逼近

1.1 对抗策略

• 明确数学本质。找到max肯定需要$n-1$n−1个“信息量”，对min同理

  在这里信息量指某个数大于/小于某个数

• 分析所有输入类型。基于上述的信息量的有无/多少，和当前的状态进行区分

• *分析状态转移。输入计算后，对原始数据的数学性质（信息量）、状态有何影响

• 找出对每次关键操作效益最低的输入类型（序列）

1.2 同时找$max \& min$max&min

两两比较，然后在胜者/败者组找max/min，最终大概$3n/2$3n/2个关键操作（比较）左右。如何证明task的下界是不是这个呢？这里同样采用对抗策略。在原始问题中，若某个数$x$x与其他数的比较结果一直是$x$x较大/小，则一直不能放弃他作为最值的可能性，而若既有较大也有较小，便可立马抛弃，从而减少计算量

1.3 找$2^{nd} max$2ndmax

考虑两两PK，第二大的数只会输给max，找到max后，在输给max的数中找max即可

---

2 Median

2.1 快排base

和快排的partition有紧密联系，简单理解，可随机选取一个中轴，一次划分后，直到中轴的$index$index是$median$median结束，否则递归

2.2 Partition Improved

本质是花一点代价选个好的标准，使得划分后两边尽量平衡。把n个数分成5个一组，每个小组partition出median，再求出median的median为$m^*$m∗

B区域的元素都比$m^*$m∗大，C都小。所以每次先找到$m^*$m∗，再用$m^*$m∗进行partition，而得到相对平衡的划分，最坏不过是$n/4和3n/4$n/4和3n/4

2.3 对抗策略

median即恰好有$n/2$n/2比它大，$n/2$n/2比它小（奇数），此时的信息量即是潜在的中位数$m^*$m∗比某个数大/小。对于信息量而言，若$m>b,b>c$m>b,b>c，则通过一次与m相关的比较，获得了两个与m有关的信息。若$m>b,c>b$m>b,c>b，则不能确定$m和c$m和c的关系，只获得了一个信息。由此构造特定的输入