我更喜欢尽可能少的正式定义和简单的数学.
algorithm complexity-theory big-o computer-science time-complexity
众所周知,heapsort的最坏情况运行时为Ω(n lg n),但我很难理解为什么会这样.特别是,heapsort的第一步(制作最大堆)需要时间Θ(n).然后是n次删除.我理解为什么每个堆删除需要时间O(lg n); 重新平衡堆涉及一个向下泡沫的操作,它在堆的高度花费时间O(h),并且h = O(lg n).但是,我没有看到为什么第二步应该采用Ω(n lg n).似乎任何单个堆出列都不一定会导致节点移动到顶部以一直向下冒泡到树中.
我的问题是 - 有没有人知道heapsort的最佳案例行为的良好下限证明？