如何利用对手论证法证明中位数问题的比较次数下界？

5个数通过6次比较求中位数的方法如下：

5个数之间的大小关系构成的一个树形图T。T中的一个结点代表一个数，而一条边代表它所关联的两个数的大小关系，T的根就是中位数。显然T中的一条边要由一次比赛来确定。在下面的图中，如果x大于y，则节点x在节点y的上方且x和y有一条边相连。另外，*表示一般的数，o表示下一次即将进行比较的两个数。

第1步，先任取两个数比较，结果为：

*
|
* o o *

第2步，再取另外两个数比较，结果为：

o o
| |
* * *

第3步，按照上图比较其中两个标记为o的数，比较结果只有一种情况：

*
/ /
* o
|
* o

第4步，按照上图比较其中两个标记为o的数，比较结果有两种情况：

* o *
/ / / / /
o * o o
| | |
* * *

第5步，按照上图比较其中两个标记为o的数，比较结果有两种情况：

* * *
/ / / / /
/ // / /
| // | /
| / / | *
| / / | | /
|/ /| | /
o o | /
| o o
| |
| |
* *

第6步，按照上图比较其中两个标记为o的数，比较结果有两种情况：

* * * * * *
/ / / / | |
x x * *
| / / | |
* * * x x
| | / /
* * * *
|
*

其中的x就是中位数。

事实上，可以证明：对于n个数求中位数，至少需要3(n-1)/2次比较，并且存在一个O(n)次比较的算法。

下面介绍如何利用对手论证方法来证明中位数问题的比较次数下界。

首先介绍“对手论证（Adversary Argument）”方法。

若用P表示所讨论的问题，I表示问题的输入，A表示求解问题P的基于比较运算的算法T(A,I)表示对于输入I算法A的计算时间复杂性，那么，函数
U(n)=min{max{T(A,I)}, for each I}, for each A，
是问题P当输入的大小为n时在最坏情况下的最好下界。它是问题所固有的。

问题P的这个最好下界通常很难按其定义计算得到，因为对于一个具体的A，要得到
max{T(A,I)}, for each I
就是一件很难的事，更何况对于一切的A。因此，人们往往不去精确地求U(n)，而是退而求其次，即找一个f(n)，它不大于U(n)但尽量地接近于U(n)，使f(n)成为问题P的一个好下界。

对手论证方法是找f(n)的一种有效方法。它的基本思想是对每一个A，构造一个输入特殊的输入I'，使T(A,I')尽量地大，然后在所有A的集合上，求T(A,I')的尽量好的下界作为f(n)。这种方法通过
f(n) <= min{T(A,I')}, for each A <= min{max{T(A,I)}, for each I}, for each A = U(n)
来保证f(n)是问题P的一个下界，又通过使T(A,I')尽量大来保证f(n)是一个好的下界。

对手论证方法的关键在于有一套对一切A都适用的构造符合要求的I'的策略，即对手策略。这种策略，逐步地构造出一个输入I'，便算法A为得到与几相应的结果，要做尽量多次的比较和判断，从而使T(A,I')尽量大。需要注意的是，一方面对手策略须具有一致性，即不能前后矛盾，以保证I'的存在性；另一方面对手策略还须对一切A都适用，因为我们需要在一切A组成的集合上求T(A,I')的下界。至于策略的具体内容将因问题而异。甚至同一个问题可能有多种策略，要得到好的下界，需要有好的策略。

中位数问题的原型是：任给n个数，要求找出它们的中位数，即第[(n+1)/2]大的数。

下面我们用对手论证方法来证明中位数问题比较次数的下界为3(n-1)/2次。

不失一般性，这里假设所给的n个数互不相同，且n为奇数。

我们用A表示求解中位数问题的任意一个基于比较的算法。对于任意给定的输入I，算法A在最后输出所要找的中位数之时，已经确定了I中哪(n-1)/2个数大于该中位数和哪(n-1)/2个数小于该中位数。我们称I中大于中位数的数为上部数，小于中位数的数为下部数。显然，算法最终从I中分出(n-1)/2个上部数和(n-1)/2个下部数，靠的是"组织"一系列的比赛。一个数最后被确定为上部数，要么曾经直接与中位数比赛过且赢了它，要么曾经与另一个上部数比赛过且赢了它；类似地，一个数最后被确定为下部数，要么曾经直接与中位数比赛过且输给它，要么曾经与另一个下部数比赛过且输给它。我们称算法中同是上部数或同是下部数之间的比赛，以及上部数或下部数与中位数之间的比赛为关键性比赛；而称算法中分别是上部数和下部数的两个数之间的比赛为非关键性比赛。注意，只有关键性比赛才能使我们获得有用的信息，非关键性比赛并不能使我们获得有用的信息。若用N1(A,I)，N2(A,I)和T(A,I)分别表示对于输人I算法A的关键性比赛次数、非关键性比赛次数和计算时间复杂性，那么我们明显有
T(A,I) >= N1(A,I) + N2(A,I)
我们的目的是给出中位数问题的一个计算时间下界，即对于所有的算法A，max{T(A,I)}的一个下界，而且希望这个下界的值尽量大。

为此，我们使用对手论证方法。对任意给定的算法A，假设他的输入为I，设M是不在I中的一个数，我们将从I出发，构造一个确定的输入I'。因为非关键性比赛不能使我们获得有用信息，是“无用”的比赛，为了得到尽量大的T(A,I')，我们构造的I'应该都使得N2(A,I')尽量地大。I中每两数x,y在进行比较前（参赛前）的状态分别用N，N'，L，S和E来表示，它们的含义依次是：

★ N : 该数未曾参加过比赛，且不是当前唯一的未参加过比赛的数;
★ N': 该数是当前唯一的末曾参加过比赛的数;
★ L : 该数已参加过比赛，且其值大于M;
★ S : 该数已参加过比赛，且其值小于M;
★ E : 该数已参加过比赛，且其值为M。

采取的对手策略如表1所示。注意,表1中的对手策略是一致的，因为I'中的数x,y只当在第一次参加比赛时（即x,y赛前状态中有N'时）才会修改x,y的值，一旦x,y的值被修改过了，以后再次参加比赛时就不再修改。表1中对手策略的关键是：当x,y第一次参加比赛时，如果该比赛可能成为关键性比赛，则修改x,y的值使得该比赛便为非关键性比赛；在遇到最后一个参赛数时，将他的值修改为预先规定的中位数M的值。

表1 中位数问题的对手策略

+========+=======+=================================+============+===============+
| x:y赛前状态 | | | x:y赛后状态 |
|--------+-------| 对 手 策 略 | 比赛类型 +-------+-------+
| x | y | | | x | y |
+========+=======+=================================+============+=======+=======+

+========+=======+=================================+============+=======+=======+
| N | N | 若x>M且y>M，则减少y，使y<M; | 非关键性 | L | S |
| | +---------------------------------+------------+-------+-------+
| | | 若x<M且y<M，则增加x，使x>M; | 非关键性 | L | S |
| | +---------------------------------+------------+-------+-------+
| | | 若x<M且y>M，则不改变x,y | 非关键性 | S | L |
| | +---------------------------------+------------+-------+-------+
| | | 若x>M且y<M，则不改变x,y | 非关键性 | L | S |
+========+=======+=================================+============+=======+=======+
| L | L | 不改变x,y | 关键性 | L | L |
+========+=======+=================================+============+=======+=======+
| S | S | 不改变x,y | 关键性 | S | S |
+========+=======+=================================+============+=======+=======+
| E | E | 此情况不可能出现 | | - | - |
+========+=======+=================================+============+=======+=======+
| N' | N' | 此情况不可能出现 | - | - | - |
+========+=======+=================================+============+=======+=======+

+========+=======+=================================+============+=======+=======+
| L | N' | 不改变x的值，令y的值为M | 关键性 | L | E |
+========+=======+=================================+============+=======+=======+
| N' | L | 不改变y的值，令x的值为M | 关键性 | E | L |
+========+=======+=================================+============+=======+=======+
| S | N' | 不改变x的值，令y的值为M | 关键性 | S | E |
+========+=======+=================================+============+=======+=======+
| N' | S | 不改变y的值，令x的值为M | 关键性 | E | S |
+========+=======+=================================+============+=======+=======+
| N | N' | 若x<M，不改变x的值，令y的值为M | 关键性 | S | E |
| | +---------------------------------+------------+-------+-------+
| | | 若x>M，不改变x的值，令y的值为M | 关键性 | L | E |
+========+=======+=================================+============+=======+=======+
| N' | N | 若y<M，不改变y的值，令x的值为M | 关键性 | E | S |
| | +---------------------------------+------------+-------+-------+
| | | 若y>M，不改变y的值，令x的值为M | 关键性 | L | L |
+========+=======+=================================+============+=======+=======+

+========+=======+=================================+============+=======+=======+
| N | L | 若x>M，则减小x，使x<M; | 非关键性 | S | L |
+========+=======+=================================+============+=======+=======+
| L | N | 若y>M，则减少y，使y<M; | 非关键性 | L | S |
+========+=======+=================================+============+=======+=======+
| L | S | 不改变x,y | 非关键性 | L | S |
+========+=======+=================================+============+=======+=======+
| S | L | 不改变x,y | 非关键性 | S | L |
+========+=======+=================================+============+=======+=======+
| N | S | 若x<M，则增加x，使x>M; | 非关键性 | L | S |
+========+=======+=================================+============+=======+=======+
| S | N | 若y<M，则增加y，使y>M; | 非关键性 | S | L |
+========+=======+=================================+============+=======+=======+

+========+=======+=================================+============+=======+=======+
| N | E | 此情况不可能出现 | - | - | - |
+========+=======+=================================+============+=======+=======+
| E | N | 此情况不可能出现 | - | - | - |
+========+=======+=================================+============+=======+=======+
| L | E | 不改变x,y | 关键性 | L | E |
+========+=======+=================================+============+=======+=======+
| E | L | 不改变x,y | 关键性 | E | L |
+========+=======+=================================+============+=======+=======+
| S | E | 不改变x,y | 关键性 | S | E |
+========+=======+=================================+============+=======+=======+
| E | S | 不改变x,y | 关键性 | E | S |
+========+=======+=================================+============+=======+=======+

根据表1的策略，I'中的数只当它在第一次参赛时才被修改，更进一步，对于由该策略构造出来的I'的n个数，其中至少有n-2个数参加了非关键性的比赛。注意到n是奇数，因此算法A对根据表1构造的输入I'所“组织”的比赛中，非关键性的比赛至少有(n-1)/2次，即
N2(A,I') >= (n-1)/2 ------ (1)
下面我们对于同一个I'来考虑N1(A,I')的界。如前所述，算法A为了找出I'的中位数，必须识别出I'的(n-1)/2个上部数和(n-1)/2个下部数。说得更具体些，算法A至少必须识别出I'的n个数之间的大小关系构成的一个树形图T。T中的一个结点代表I'中的一个数，而一条边代表它所关联的两个数的大小关系，T的根就是中位数。显然T中的一条边要由一次比赛来确定，又因为一棵n个结点的树有n-1条边，因此T至少要有n-1次比赛才能够确定，而且这些比赛都必须是关键性的比赛。于是，我们有
N1(A,I') >= n-1 ------ (2)
综合(1)(2)式可知:
max{T(A,I)} >= T(A,I') = N1(A,I') + N2(A,I') >= 3(n-1)/2
从而得到中位数问题的比较次数下界为3(n-1)/2。

至于最坏情况下O(n)次比较的选择第k大元素的算法，说起来比较麻烦，暂时就不说了（打字太累~~）