题7

题7

题目

Q:构建 个记录的初始堆，其时间复杂度为 ( ) ；
对 个记录进行堆排序，最坏情况下其时间复杂度为 ( ).
A. B. C. D.

分析

A:正确答案是：

• 构建 个记录的初始堆，其时间复杂度为 A. 。
• 对 个记录进行堆排序，最坏情况下其时间复杂度为 D. 。
  解释:

1. 构建初始堆 - : 虽然构建堆的过程中需要进行“向下调整”操作，而每次调整的时间复杂度看似是 ，但实际上，并不是所有节点都需要调整这么多层。
   • 只有靠近根节点的少数节点需要调整 层。
   • 绝大多数节点都位于堆的底层，只需要调整很少的层数，甚至不需要调整。
   • 总体来说，构建初始堆的比较次数和交换次数都和 成线性关系，因此时间复杂度是 。
2. 堆排序 - : 堆排序主要包含两个阶段：
   • 构建初始堆: 如上所述，时间复杂度为 。
   • 输出堆顶元素并调整堆: 这个过程需要执行 次。
   • 每次操作都需要将堆顶元素与最后一个元素交换，然后将新的堆顶元素向下调整至合适的位置，这一步的时间复杂度是 。
   • 因此，该阶段的时间复杂度是 ，也就是 。
     由于堆排序的时间复杂度主要由第二个阶段决定，因此总体的时间复杂度是 。

解

A、D
建堆过程中,向下调整的时间与树高 有关,为 。
每次向下调整时,大部分结点的高度都较小。
因此,可以证明在元素个数为 的序列上建堆,其时间复杂度为 。
无论是在最好情况下还是在最坏情况下,堆排序的时间复杂度均为 。