以前在看算法导论时，一直有个问题：为什么比较排序至少要比较nlgn次，而基数排序只需要O(n)次操作就可以。对于前者，算法导论画

了一个lgn高的决策树来证明，却不能从本质上回答我的问题；而后者，我从没找到任何解释。
    最近由于项目的原因，浅学了下信息熵理论。借此，可很好的解决上述的问题(发挥下伍子胥精神^)。
    排序是把N个无序的数字按顺序排列，N个数字总共有N!(1乘到N)的排序，而排序结果是唯一的(不失一般性，我们认为N个数字中没有相同

的)。
    对于比较排序，其每次比较产生两个结果:大于或小于，记为x(x={大于，小于})(好吧，这个符号的意思是，x的取值范围是大于或小于^)

。现在问题是，多少个x(即多少次比较)可以唯一决定一个N个数字的排列？
    根据鸽洞原理，要唯一决定一个排列，x的个数k必须满足如下条件：2^k>N!(2的x次方)，解得k=O(NlgN)，好吧，似乎有点眉目了。
    但还不是最终(不然就叫鸽洞原理而不是信息熵理论了)。
    根据信息熵理论，x的可取两个值，其信息量是lg2。而N个数字有N!种排序，其信息量为lgN!需要多少个x决定一个排序呢？好吧，
k = lgN!/lg2 = O(NlgN)。
    据此，对于基数为n的基数排序(非比较排序)，由于其每次操作的结果是有个n(尾数是0到n-1),故其信息量为lgn,因此k = lgN!/lgn.而一

般非比较排序lgN/lgn是一个较小的常数(如1^^，即n=N)，因此k = lgN!/lgn = O(N).
    现在明白了吧^^。余下的问题是，为啥用lgn来表示有n个选择的变量的信息量？如想知道，自己去看信息熵理论吧，相信会非常有用的。

　　有一次看电影，大约是在西湖影院，一个韩国的片子“外出”，电影的情节不记得了，
只记得片尾是纳尼亚传奇的预告片，精彩纷呈（后来看了才知道，预告片这玩意儿，就
像NBA的剪辑一样，阿联看起来像dirk)。当时L就说，下回我们看这个吧。
　　后来，好像因为外出是个不祥的片子，我不得不一个人看纳尼亚传奇，就像我通常做
大部分事情一样。
　　我已习惯了独自行动。我很习惯一个人抱个篮球去球场，和11个不认识的人打4对4，
有那么几次和warrior一起去了，那几场我变成了内线。我不习惯和同学一起去吃饭，两个
人太不方便了，清华的食堂，找个位子都费劲，Andrew Yao吃饭还那么快。不过似乎我还
是渴望与人交流的：无聊的时候与星际为伴，或者在QQ上和co互骂，或者review
下毕老师的邮件（我总是回头才看他发的附件）。
　　总之，虽然大多数时候与人在一起，但我总是独立做事情。在公司我做独自的项目，
边上不知哪个TEAM整天在讨论，而我只需要与自己讨论，有不懂的可以问pete。pete哥是
个非常好的人，在去AOL之后我就不再找工作，很大一部分原因是因为他。有这么nice的
mentor，是我的幸运。
　　幸运不只这些。当年我在浙大遇到了极品的导师李际军同志（我甚至不想把这
个名字马赛克一下），而上天很快把哨吹了回来，在清华我遇到了两位好的导师：Pro.Liu
和Pro.Bi.两位老师对我的帮助是不可估量的，我永远不会忘记。
　　我不会忘记的还有其他人。Andrew Yao吃饭快且老实，XLZ能力一流，x.leng反应快
到我不懂，seawing和warrior去了SK还帅。。。我必须额外提几个人，我差点忘记了sqq，
那天我听到那首“不想长大”，就记起了你。我还想起了lhx，syy，我有时候会在无预兆
的情况下梦到，但我也梦到过徐凯和张照兵。梦就像那些无脑的艺人的话一样，你永远不
知道是怎么回事（就像这句话一样＾）。
　　即将离校，没有伤感，值得庆幸。与上一次的离校不同（反正现在工作就在校门口）。
听宇杰说，当年辛离开浙大的时候，他们班的人都去送了，而我没有。我想，我不送她，
应该是对她最好的送别吧。
　　上天的确像是NBA的裁判，无法准确的判罚，只有通过吹回头哨的方法来补过。感谢上
天对我的回头哨。10年如梦，如花安在？轮子继续滚动。
　　纳尼亚传奇2来了，感觉像是上个世纪的回忆，或者是上个轮回。我看着外出，等待
纳尼亚传奇，却等来了真正的外出；如今，我又是看着外出2，等待着纳尼亚传奇2。跟我做
个交易吧：与我同看此片，我跟你结婚。