堆排序时间复杂度

Question

堆排序，删除操作复杂度O(lgN)，删除操作次数为N，但是每次删除后N都会减一。所以应该是：
lg(N)+lg(N-1)+…+lg2+lg1 = lg(N!)
然后根据lgN!公式：
lgN！=(lg(2pi)+lgN)/2+N(lgN-lge);

得出O(lg(N!)) = O(NlgN)

但是基本都直接写结果为O(NlgN)，是默认这样，还是我的思路是错的？

lgN!公式详情:http://www.cnblogs.com/zhangshu/archive/2011/08/12/2135855.html

Answer 1

O 是上界， log(n!) <= log(n^n)，自然是有道理的。
堆排序是基于比较的排序，下界是 nlogn

上下界都一样，应该可以说明复杂度就是 nlogn

题主通过 sterling formula 证明的办法更直接： log(n!) 和 nlogn 是一样的。

Answer 2

换一种思路来计算更简单：不考虑每次删除后N-1

log(N) +　log(N) + ... + log(N) = log(N^N) = NlogN