顺便可以证明一下对于所有的randomized sorting algorithm，比较次数的lower bound也是nlgn。http://en.wikipedia.org/wiki/Randomized_algorithm
决定把这个放到下一篇文章中讲。O(∩_∩)O~
后面举几个例子来简单具体阐述一下上面说的两个方法。
例 有两个长度为n的已经排好的list，a1
假设我们用adversarial strategy证明，假设我们只比较了2n-2次，也就是我们只想神询问了2n-2次，这时我们知道有一个元素ai，他一定是没有和bj或者是bj+1比较的，假设我们的ai = 2i-1，也就是所有的奇数，bi = 2i，所有的偶数，那么这个时候，我们的算法已经给出了output，但是对于无所不能的神来说，它知道你没有比较ai和bj或者是没有比较ai和bj+1。
如果你没有比较ai和bi，你输出的是aibi，但是神可以交换ai和bi的值，这个时候ai = 2i，bi = 2i-1，交换的同时，依然保证a1 同理，如果你没有比较ai和bi+1，神依旧可以交换ai和bj+1的值，导致你的算法还是错的，所以你的2n-2的算法悲剧了，所以证明lower bound是2n-1。 例 给定一个长度为n的已经排好的list，a1 这个我们可以用decision tree的方法找到这个lower bound，考虑下面的decision tree： 从这个树上我们可以得出： 1）对于每一个非叶子节点，都有两个分支。 2）这个树一共有n个叶子节点（对应了我们n个可能的答案） 假设树的高度是h，我们知道最多可能出现的叶子节点数是 2^0+2^1+2^2+。。。+2^k-1，这是等于2^k-1的，当然，这个是大于等于n的，所以，就有 2^k-1 >=n, 可以得到 k >= lg(n+1)，这也就是，一路比较下去我们至少要用 lg(n+1)次比较。 