[Algo][July]基于比较排序的算法下界是O(nlogn)

假设：有n个数需要排序。

n个数的全排列方式是A(n,n) = n!

基于比较，i<j. 在最优的情况下，可以在n!个可能中筛去一半。 也就是说剩下(n!/2)种可能.

这样的比较方式进行k次。最后筛出一种（符合要求的）排序:

　　n!/(2^k) < 1

公式推导：

　　2^k > n!                 //我理解就是k表示要筛多少次，2^k是排列的可能性。那么2^k要大于n!，才能保证筛的时候包含了那个正确的排列。

　　klog(2) > log(n!)  //两边取对数

　　k > log(n!)           //忽略常数

　　n!<nⁿ => log(n!)~nlog(n)

　　nlog(n)是log(n!)的等价无穷大。数学证明参考：

       http://blog.csdn.net/justdoithai/article/details/51531332

之所以可以用等价无穷大替代，是跟大O()函数相关，即时间复杂度计算方式：

参考：https://baike.baidu.com/item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6

.一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

需要高数基础，还有求极限的知识。

推得：

　　k > nlog(n)         //所以nlog(n)是下界