建堆的时间复杂度O(N)

返回顶部
查看留言
转到底部

现在的位置: 首页 > 综合 > 正文

建堆的时间复杂度O(N)

2013年12月02日 ⁄ 综合 ⁄ 共 200字 ⁄ 字号小中大 ⁄ 评论关闭

首先这个循环是从i = headsize/2 -> 1，也就是说这是一个bottom-up的建堆。于是，有1/2的元素向下比较了一次，有1/4的向下比较了两次，1/8的，向下比较了3次，......，1/2^k的向下比较了k次，其中1/2^k <= 1, k 约等于lg(n)。于是就有总的比较量：

T = ( $\sum_{k = 1}^{lg(n)}{{1 \over {2^k}} \times k}$ )
* n

令 S = $\sum_{k = 1}^{lg(n)}{{1 \over {2^k}} \times k}$

1/2 S = $\sum_{k = 1}^{lg(n) - 1}{{1 \over {2^{k+1}}} \times k} = {1 \over 4} + {1 \over 8} \times 2 + \cdots + {1 \over {2^{k+1}}} \times k$
S - 1/2S = 1/2S = ${1 \over 2} + {1 \over 4} + \cdots + {1 \over {2^k}} - {1 \over {2^{k+1}}} \times k$
到这步就很明显了吧，S <= 2
于是T <= 2n => T = O(n).