数据结构——完全二叉树时间复杂度讲解,堆排序

目录

一. 构建堆的时间复杂度分析

1. 基于向上调整策略的堆构建方法

2. 采用向下调整策略的堆构建方法

二. 堆排序技术

1. 基本概念阐述

2. 算法设计思路

3. 具体代码实现过程

---

一.建堆的时间复杂度

1.向上调整算法建堆

我们以极端情况来分析时间复杂度，即考虑满二叉树结构并遍历所有层级的情形。

设系统中节点总数为N，树结构的高度为h

N = 2^0 + 2^1 + 2^2 + ... + 2^(h-1)

由此可得N = 2^h - 1

进而推导出h = log(N+1)

在衡量时间复杂度时，我们以交换操作的次数作为评判标准

1 0

2 2^0 * 2^1

3 2^1 * 2^2

...

h 2^(h-2) * 2^(h-1)

F(h) = 2^0 * 2^1 + 2^1 * 2^2 + ... + 2^(h-2) * 2^(h-1)

= 2^h * (h - 2) + 2

F(N) = (N+1)(log(N+1)-2)+2（此为精确的时间复杂度表达式，通常可简化表示为O(N*logN