log(n!) = O(nlogn)

[jaze lee]

这个是怎么算出来的啊？或者需要看哪方面的资料，能理解这个？谢谢

[Wén Shào]

我肯定首先用 stirling approximation，然后估计就能看到你要的答案了。 

Cheers, 

Wén

2011/11/10 jaze lee <jaz...@gmail.com>

这个是怎么算出来的啊？或者需要看哪方面的资料，能理解这个？谢谢

[Ce Zhang]

Stirling 公式

在 2011年11月10日 下午6:21，jaze lee <jaz...@gmail.com>写道：

这个是怎么算出来的啊？或者需要看哪方面的资料，能理解这个？谢谢

--
Best Regards.

----------------------------------------------------------------------------------

Ce Zhang

Hi-Tech Innovation Centre(HITIC)
Institute of Automation，Chinese Academy of Sciences.
Addr: Beijing，100190，P.R.China
Tel:   (+86) 158-1138-5087       MSN:  czhan...@live.cn

[Jinwu Li]

http://stackoverflow.com/questions/2095395/is-logn-nlogn

基本高数,放缩法

2011/11/10 Ce Zhang <ecg...@gmail.com>:

[庞彦]

logn(n-1)(n-2)....1 = logn + log(n+1) + ...+ log1 <= nlogn
建议看张筑生或者江泽坚的数学分析

--
我是haithink

[Jaze Lee]

谢谢，各位啊，明白了 log(n!) = O(nlogn)的道理， 但是在看 

  “所有基于比较的排序算法，其复杂度为什么是以O(nlogn)为下界的，因为一次比较操作最多有两个结果，a>b或a<b，既然只有两种结果，那么最多只能将解空间进行2分，如果每次都能完美的2分，那么找到那个唯一点最终需要的步骤就是log(n!) = O(nlogn)” 

这个还是不明白， 什么叫最多只能将解空间进行2分啊？ 能不能举个实际点的例子啊？

[张小鱼]

关于这个2分，可以这么理解，排序的解空间就是所有元素的一个全排列

一次比较之后，就可以排除其中一半的无效排列

比如如果a>b，那么所有b在a前面的排列都是无效的

 

我想下面这个文章已经说得非常明白了：

http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/

 

 

发件人: pon...@googlegroups.com [mailto:pon...@googlegroups.com] 代表 Jaze Lee
发送时间: 2011年11月11日 13:33
收件人: pon...@googlegroups.com
主题: Re: [TL] log(n!) = O(nlogn)

[Jaze Lee]

那为什么是最多是二分呢？

[王明辉]

可以这么理解,仅知道a<b或a>b的话,如果想三分,信息量是不够的,没有办法确定在三个中的哪一个中.

--

Best regards,

祝好,

纳米黑客

nami...@gmail.com

namiheike.com

[shicker]

仅仅想要理解的话 还不如这么想 当n趋向无穷大的时候 n! 趋向于n的n次方

[Jaze Lee]

在 2011年11月12日 上午9:29，王明辉 <nami...@gmail.com>写道：

可以这么理解,仅知道a<b或a>b的话,如果想三分,信息量是不够的,没有办法确定在三个中的哪一个中. 

 我感觉 最多二分不是这个意思吧，感觉应该是 比较最好的情况是能够把解空间二分，哪个以比较为基础的算法，能够每一次都吧
解空间给二分，那么这个算法就是最好的算法。可惜没有一个这样的算法