为何log(n!)的时间复杂度是O(nlogn)而非O(log(n!))？

核心结论 #

其实完全可以用O(log(n!))表示时间复杂度，但行业和教科书更偏爱用O(n logn)这类标准形式，本质是为了统一语言、简化对比，而非“不能用”。

为什么不用O(log(n!))？ #

• 渐近等价性：根据斯特林公式，log(n!) ≈ n logn - n + O(logn)，这意味着当n趋向无穷大时，log(n!)和n logn的增长速率完全一致，属于同一个Θ等价类（即两者互为上下界）。用O(n logn)和O(log(n!))描述的是同一个复杂度级别，没有本质区别。
• 通用性与直观性：n logn是行业公认的标准复杂度类别之一，所有开发者和学习者都熟知它的增长特性，以及它和其他标准类别（比如n、n²）的快慢关系。如果用O(log(n!))，很多人需要先推导或回忆斯特林公式才能理解其增长速率，增加了沟通成本。

为什么教科书偏爱f(n) ~ O(g(n))且f(n)≠g(n)的形式？ #

这是渐近复杂度分析的核心目的决定的：

• 聚焦核心增长趋势：复杂度分析的本质是描述算法在数据规模n趋近无穷时的增长快慢，而非精确计算运行时间。比如一个算法的实际运行时间是5n logn + 100n + 200，低阶项（100n）和常数（200）在n很大时对整体增长的影响可以忽略，所以我们用O(n logn)来代表这个算法的核心增长趋势。
• 统一分类标准：将无限多的复杂度表达式归类到有限的标准类别（logn、n、n logn、n²、n³、2ⁿ等），能让不同算法的复杂度对比变得极其直观。比如你说算法A是O(n logn)，算法B是O(n²)，所有人都能立刻判断A比B更适合处理大规模数据，无需纠结具体的系数或低阶项。

关于《Is log(n!) = Θ(n·log(n))?》这个问题 #

这个问题的本质是在确认log(n!)和n logn属于同一个渐近等价类，从而给大家一个明确的结论：当我们用n logn代替log(n!)时，不会丢失任何关于增长趋势的关键信息。这不是说O(log(n!))不对，而是说用O(n logn)更符合行业的通用表达习惯，能让沟通更高效。

内容的提问来源于stack exchange，提问作者Sandeep T