n与log(n!)谁的渐近量级更大？O(log(n!))是否比O(n)渐近更慢？

你的判断是错误的，O(log(n!))的渐近增长速度远快于O(n)，log(n!)的渐近量级更大。

方法1：斯特林公式近似 #

斯特林公式给出了阶乘的渐近近似：
ln(n!) ≈ n ln n - n + O(ln n)
忽略低阶项后可以得到log(n!) = Θ(n log n)，对数的底数仅影响常数系数，不会改变渐近阶，因此log(n!)属于超线性量级，明显高于线性的n。

方法2：初等不等式放缩 #

不需要斯特林公式也能通过放缩得到结论：

• log(n!) = log(1) + log(2) + log(3) + ... + log(n)
• 取总和中后一半的项（即从⌈n/2⌉到n的对数），这部分共有⌊n/2⌋项，每一项的取值都大于等于log(n/2)
• 因此总和满足 log(n!) ≥ (n/2) * log(n/2) = (n/2)(log n - log 2)
• 忽略常数项后，这个下界就是Θ(n log n)，远大于线性的n

当n趋向无穷大时：

• n属于线性量级Θ(n)
• log(n!)属于超线性量级Θ(n log n)

显然n log n的增长速度远快于n，因此log(n!)的渐近量级更大，你猜测的「O(log(n!))比O(n)增长更慢」的结论不成立。

内容的提问来源于stack exchange，提问作者Charan Shetty