堆排序时间复杂度
堆排序，删除操作复杂度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
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
O 是上界， log(n!) <= log(n^n)，自然是有道理的。
堆排序是基于比较的排序，下界是 nlogn
上下界都一样，应该可以说明复杂度就是 nlogn
题主通过 sterling formula 证明的办法更直接： log(n!) 和 nlogn 是一样的。
换一种思路来计算更简单：不考虑每次删除后N-1
log(N) + log(N) + ... + log(N) = log(N^N) = NlogN