比较排序与计数排序时间复杂度的证明

比较排序对于任意的比较排序算法,我们都能将其操作抽象成一颗决策树,这是一颗完全二叉树,它表示了某一排序算法对所有元素的比较操作。下图是插入排序的例子:每一条路径都是一种可能性,所以算法的最坏情况下的排序次数就是决策树的高度。n个元素,可能的排序结果有A(n,n-1)=n!种,假设此时的树高为h,则叶子节点最多为2^(h+1)2^(h+1) ≥ n! h + 1 ≥ log2(n!)而 log(n!) = O(nlogn)。证明:不等式缩放log(n!) = log1 + ... + l...

虚骄之气与狭隘的国家主义

摘取《美国十讲》中第十讲 美国与中国的几句话,很适合当下:把自己所有的缺点,就是我们发生的坏事情和国内的问题,都怪在外国人身上,这是一种很没出息的表现。所谓“境外敌对势力”也被滥用。把自己国内的问题,由于社会不公而出现的不平之鸣,都说成是“境外敌对势力”策动的。我们的主流媒体很喜欢夸耀国力,或有选择地、断章取义地转载外国人吹捧中国的话,这会误导公众。中国过去的仁人志士都是有很深的忧患意识,而现在改革开放以后起来的一代人,忧患意识比较少,对实际国情缺乏了解,这是很危险的,但是这不能怪年轻人。...