建堆时间复杂度的计算

作者: 你今天作业做了吗 | 来源:发表于2019-04-22 10:52 被阅读0次

建堆时间复杂度的计算
【排序】堆排序-1
建堆O(n)时间复杂度证明
Java基础（3）排序
最新BAT的实习面经
算法初步
算法复杂度速查表
数据结构与算法 - 时间复杂度与空间复杂度
算法复杂度
二叉平衡树算法的时间复杂度

建堆时间复杂度的计算

建堆的方式有两种，比较常见的建堆方式是自底向上，因为时间复杂度更低，为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$ .

建堆时间复杂度的计算
建堆时间复杂度的计算建堆的方式有两种，比较常见的建堆方式是自底向上，因为时间复杂度更低，为O(N). 自顶向下的...
【排序】堆排序-1
maxHeapify() 维护最大堆性质的关键，时间复杂度 buildMaxHeap() 建堆，线性时间复杂度 h...
建堆O(n)时间复杂度证明
建堆复杂度先考虑满二叉树，计算完全二叉树建堆复杂度基本相同。对满二叉树而言，第i层(根为第0层)有2^i个节点。...
Java基础（3）排序
1、堆排序时间复杂度：O(NlogN) 这里可以分解为两个过程：建堆、进行排序 ①建堆：实际上是一个Insert...
最新BAT的实习面经
一、今日头条：后台开发面经一面，比较基础自我介绍实习经历 HashMap 堆排，建堆的时间复杂度，O(n)，...
算法初步
时间复杂度时间复杂度是用来估计算法运行时间的式子（单位）。时间复杂度小结空间复杂度用来计算一个算法临时占用...
算法复杂度速查表
方便大家快速计算常见算法的时间和空间的大O复杂度图例数据结构操作数组排序算法图操作堆操作大O复杂度图表
数据结构与算法 - 时间复杂度与空间复杂度
前言时间复杂度：时间复杂度的计算并不是计算程序具体运行的时间，而是算法执行语句的最大次数。空间复杂度：类似于时间...
算法复杂度
算法的复杂度是以什么来度量的？算法的复杂度是以时间复杂度和空间复杂度来计算的。 ①算法的时间复杂度 ...
二叉平衡树算法的时间复杂度
我们在计算时间复杂度的过程中，查找单个元素总是会出现的时间复杂度，这个时间复杂度如何计算得来的？我们在二叉平衡树中...

建堆时间复杂度的计算

建堆时间复杂度的计算

相关文章

建堆时间复杂度的计算

【排序】堆排序-1

建堆O(n)时间复杂度证明

Java基础（3）排序

最新BAT的实习面经

算法初步

算法复杂度速查表

数据结构与算法 - 时间复杂度与空间复杂度

算法复杂度

二叉平衡树算法的时间复杂度

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读