建堆时间复杂度的计算

2019-04-22 本文已影响0人你今天作业做了吗

建堆时间复杂度的计算

建堆的方式有两种，比较常见的建堆方式是自底向上，因为时间复杂度更低，为O(N).

自顶向下的建堆方式
该建堆方式是从根节点开始，然后一个个的插入堆的末尾，向上进行调整。假设堆的高度为 $h$ ，每层节点数为 $n_i$ , 每层的高度定义为该层到堆的根节点的层数，设为 $h_i$ .每层的调整的时间复杂度为 $t(n_i) = n_i (h_i - 1)$ .
则该建堆方式的时间复杂度为

$\begin{array} \\ t(n) = \sum_{i=1}^{h}t(n_i) = \sum_{i=1}^{h} n_i (h_i - 1) \\ = \sum_{i=1}^{h}2^{i-1}·(i-1) = \sum_{i=0}^{h-1}2^i·i \end{array}$

由于上述为差比数列之和，使用错位相减法即可求得结果，即

$t(n) = (h-2)·2^{h}+2$

假设该堆理想情况下为满二叉树，则存在 $h = log_2(n+1)$ ，即 $n+1=2^h$ ,则有

$t(n)=\{log_2(n+1)-2\}·(n+1)+2$

即时间复杂度为
$T(n) = nlogn$

自底向上的建堆方式
该建堆方式是从倒数第二层的节点（叶子节点的上一层）开始，从右向左，从下到上的向下进行调整。

同样的，假设该堆为满二叉树，堆高为 $h$ 。同样的，假设每层高度为 $h_i$ , 每层结点数为 $n_i$ , 则建堆复杂度为 $t(n) = \sum_{i=1}^{h-1}n_i·h_i$ , 则有

$\begin{array} \\ t(n) = 1\times (h-1) + 2 \times (h-2) + 4 \times (h-3) + ... + 2^{h-2} \times 1 \\ =2^0\times (h-1) + 2^1 \times (h-2) + 2^2 \times (h-3) + ... + 2^{h-2} \times 1 \end{array}$

同样的，该数列和为差比数列。因此，可以用错位相减法，得到时间复杂度为

$t(n) = 2^h - h - 1 = n - log(n+1).$

即，时间复杂度为 $T(n) = n$ .

建堆时间复杂度的计算

建堆时间复杂度的计算

猜你喜欢

热点阅读