称球、快排、找最大最小数的信息量分析

1、给你N个人，你通过问是不是的问题查到某个人。
前提：所有人都有可能是，即等概率。

站成一排，你一个一个问“这个？”，每次只能判断出1/N是或者(N-1)/N不是，最坏情况要比较所有；
站成两排，你问“这排？”，每次能判断出1/2是或者1/2不是，再继续将上面是的那一对分成两队，又可以判断出哪1/2是……
于是，你每次使用了已知信息，可以在log^2{N!}次比较后得出结果；而朴素的逐个比较则要N次。

其中，log^2{N!}近似于NlogN，参考证明：
http://en.wikipedia.org/wiki/Stirling%27s_approximation


综述，对于等概率的问题，
“最好的问题”就是那些能够均分所有可能性的问题，因为那样的话不管问题的答案如何，都能排除掉k-1/k，其中k为问题的答案有多少种输出。

2、排序：一组随机的N个数字，它们一共有N!种排列，其中只有一种排列是满足题意的。以下举例升序排列。

任何基于比较的排序的基本操作单元都是比较两个元素a、b，结果a小于b或者a不小于b。也就是说，每次比较最多可以将解空间切成2部分。
每次排除掉N!中的1/2，则可以在log^2{N!}~NlogN次比较后得到结果，这也是快速排序的平均时间复杂度。
但是，事实上，首次比较a0与pivot是（不妨假设是）等概率的，结果只有
a0<pivot或者a0>=pivot，到了下一个不再只有2种输出了，可能为
a1<a0<pivot、a0<a1<pivot……
并没有排除1/2，因此快排的最好情况与最快情况并不都是NlogN。


3、12个小球，其中有一个是坏球。有一架天平。需要你用最少的称次数来确定哪个小球是坏的并且它到底是轻还是重。
这个问题是一道流传已久的智力题。网络上也有很多讲解，还有泛化到N个球的情况下的严格证明。

天平的输出结果有三种“平衡、左倾、右倾”，即可以将所有的可能性切成三份，我们应当尽量让这三个分支概率均等，即平均切分所有的可能性为三等份。
如此一来的话一次称量就可以将答案的可能性缩减为原来的1/3，三次就能缩减为1/27。而总共才有2*12 = 24种可能性，所以理论上是完全可以3次称出来的。

只要记着:你选择的称法必须使得当天平平衡的时候答案剩下的可能性和天平左倾（右倾）的时候答案剩下的可能性一样多。
实际上，这等同于你得选择一种称法，使得天平输出三种结果的概率是均等的，因为天平输出某个结果的概率就等同于所有支持这个结果（左倾、右倾、平衡）的答案可能性的和，并且答案的每个可能性都是等概率的。
MacKay在他的书《Information Theory: Inference and Learning Algorithms》
http://users.aims.ac.za/~mackay/itila/book.html（电子书）
里面4.1节专门讲了这个称球问题。

也可以参考这篇文章的分析：
http://users.aims.ac.za/~mackay/sorting/sorting.html


4、同时找最小元素、最大元素，时间下界为(3/2 * N - 2)，同样基于比较和信息量的累积，根据已有的知识做出认知判断。
一般，找出最大，至少需要N-1个与之比较，因此下界N-1；同样找出最小，下界N-1；算来，总的时间2*N-1。

事实上，其中有些信息量没有使用。任两个数比较，其中大的必然不可能为最小的，小的不可能最大。
即，其余N-2个元素的关系对于所求结果信息量不增加，它们的判断是浪费。
舍去这些无用功，可以得到
N-1 + N - ceil((N-2)/2) = ceil(3N/2)
这些比较全部是必须的，这就是最少比较次数，即下界。

那么，对于这个结果，怎么实现？
分而治之，分成两列，各取一个两两比较；大的与大的又分成一组，再分，再比；小的与小的又分成一组，……

N/2 + 2*N/4 + 2*N/8 + …… = ceil(3N/2)

或者看递归树，可以知道，比较次数为ceil(3N/2)，与理论分析吻合。

将问题量化，也是一种不错的解决问题的角度。