为什么堆排序算法的时间复杂度是O(n logn)？关于求和推导的疑问

你的核心误解在于：O(log(n!))和O(nlogn)是完全等价的渐近时间复杂度，并不是前者比后者更小，这也是为什么两种表述都能用来描述堆排序的总时间复杂度。

具体来说：

• 我们可以用斯特林公式推导阶乘的对数的渐近行为，斯特林公式对阶乘的近似为：
  n! ≈ n^n e^{-n} \sqrt{2\pi n}
  对两边取对数（无论以2还是自然对数e为底，都不影响渐近阶的结果），可得：
  log(n!) ≈ nlogn - n + (1/2)log(2πn)
  当n趋近于无穷大时，nlogn是其中的主导项，剩下的-n和对数项相对于nlogn来说可以忽略不计，所以log(n!)的增长速度和nlogn完全一致。
• 行业里更常用O(nlogn)来表述，是因为这个形式更简洁直观，方便和其他排序算法（比如归并排序、快速排序的平均复杂度）做对比，而O(log(n!))需要额外理解阶乘的对数特性，所以前者成为了更通用的表述方式。
• 回到你提到的堆操作：每次移除根节点后调整堆的时间确实是O(logi)（i为当前堆的元素数量），总时间是sum_{i=1}^n logi = log(n!)，但由于它和O(nlogn)渐近等价，所以我们也可以直接用O(nlogn)来描述总时间复杂度，这两种说法没有本质区别。

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