文档章节

堆排序中建堆时间复杂度

huser_YJ
 huser_YJ
发布于 2014/09/22 16:38
字数 600
阅读 484
收藏 1

如果仅从代码上直观观察,会得出构造二叉堆的时间复杂度为O(n㏒n)的结果,这个结果是错的,虽然该算法外层套一个n次循环,而内层套一个分治策略下的㏒n复杂度的循环,该思考方法犯了一个原则性错误,那就是构建二叉堆是自下而上的构建,每一层的最大纵深总是小于等于树的深度的,因此,该问题是叠加问题,而非递归问题。那么换个方式,假如我们自上而下建立二叉堆,那么插入每个节点都和树的深度有关,并且都是不断的把树折半来实现插入,因此是典型的递归,而非叠加。


在做证明之前,我们的前提是,建立堆的顺序是bottom-top的。

正确的证明方法应当如下:


1. 具有n个元素的平衡二叉树,树高为㏒n,我们设这个变量为h。

2. 最下层非叶节点的元素,只需做一次线性运算便可以确定大根,而这一层具有2^(h-1)个元素,我们假定O(1)=1,那么这一层元素所需时间为2^(h-1) × 1。

3. 由于是bottom-top建立堆,因此在调整上层元素的时候,并不需要同下层所有元素做比较,只需要同其中之一分支作比较,而作比较次数则是树的高度减去当前节点的高度。因此,第x层元素的计算量为2^(x) × (h-x)。

4. 又以上通项公式可得知,构造树高为h的二叉堆的精确时间复杂度为:

S = 2^(h-1) × 1 + 2^(h-2) × 2 + …… +1 × (h-1)  ①


通过观察第四步得出的公式可知,该求和公式为等差数列和等比数列的乘积,因此用错位想减发求解,给公式左右两侧同时乘以2,可知:

2S = 2^h × 1 + 2^(h-1) × 2+ …… +2 × (h-1)      ②


用②减去①可知: S =2^h × 1 - h +1        ③


将h = ㏒n 带入③,得出如下结论:


S = n - ㏒n +1 = O(n)


所以我们可以得出结论:构造二叉堆的时间复杂度为线性得证。


另外在算法导论78页也有证明,不过用到的方法不一样。


© 著作权归作者所有

huser_YJ
粉丝 2
博文 21
码字总数 28816
作品 0
武汉
私信 提问
加载中

评论(1)

skyler1
skyler1
楼主,“由于是bottom-top建立堆,因此在调整上层元素的时候,并不需要同下层所有元素做比较,只需要同其中之一分支作比较,而作比较次数则是树的高度减去当前节点的高度。因此,第x层元素的计算量为2^(x) × (h-x)”
这里没有看明白呢,请教
自己动手实现java数据结构(八) 优先级队列

1.优先级队列介绍 1.1 优先级队列   有时在调度任务时,我们会想要先处理优先级更高的任务。例如,对于同一个柜台,在决定队列中下一个服务的用户时,总是倾向于优先服务VIP用户,而让普通...

小熊餐馆
02/28
0
0
Leetcode【347、378、451、692】

问题描述:【Heap】347. Top K Frequent Elements 解题思路: 给一个整数数组,返回最常出现的 k 个元素。 一般情况下,求前 k 个元素的题目可以使用堆求解。但是如果先进行堆排序(O(n*log...

牛奶芝麻
06/30
0
0
深度剖析八大经典排序算法—C++实现(通俗易懂版)

内容会持续更新,有错误的地方欢迎指正,谢谢! 引言 该博客的示例代码均以递增排序为目的~ 学习建议:切忌看示例代码去理解算法,而是理解算法原理写出代码,否则会很快就会忘记。 算法分类 ...

billcyj
2017/11/06
0
0
数据结构系列(6)之 完全二叉堆

本文将主要讲述在堆排序和优先级队列中使用的一种数据结构,二叉堆; 一、结构概述 完全二叉堆,首先在逻辑上是树形结构,完全二字则表明是完全的二叉树,其结构如图所示: 结构性: 正是因为...

三枣
04/17
0
0
十种常见排序算法

1.常见算法分类 十种常见排序算法一般分为以下几种: (1)非线性时间比较类排序:交换类排序(快速排序和冒泡排序)、插入类排序(简单插入排序和希尔排序)、选择类排序(简单选择排序和堆...

architect刘源源
2018/01/28
14
0

没有更多内容

加载失败,请刷新页面

加载更多

安全组和云防火墙的区别

前言 熟悉云平台的朋友可能都会注意到这样一个事情:无论公有云还是私有云,创建虚拟机的时候都需要选择安全组,来对虚拟机进行安全防护;有的云平台在VPC里,还能选择防火墙,ZStack在3.6版...

ZStack社区版
22分钟前
2
0
教育性app开发的重要性和好处

在这个精通技术的世界中,流行的app主导着无聊的教育系统。当我们将技术和教育结合在一起时,它将带来当代以及强大的学习资源。因此,将教育移动app集成到您的学习过程中,并根据自己的信念把...

a429011717
23分钟前
3
0
IE6/7/8如何兼容CSS3属性

本文转载于:专业的前端网站➩IE6/7/8如何兼容CSS3属性 最近在工作中总是要求IE8兼容CSS3属性,在网上搜了搜主要是引入了一个htc文件(ie-css3.htc或者PIE.htc。个人认为这两个文件的作用差不...

前端老手
39分钟前
3
0
手把手教你ALLEGRO的约束规则的设置教程!

约束规则的设置 分三步, 定义规则(一、基本约束规则设置:1、线间距设置;2、线宽设置;3、设置过孔;4、区域约束规则设置;5、设置阻抗;6、设置走线的长度范围;7、设置等长:7.1、不过电阻的NET 等...

demyar
40分钟前
4
0
完美解决H5滚动滑动穿透方案:不使用系统滚动

网上有很多黑科技解决这个问题,都不是从根本去解决,例如通过js控制弹出时html加上position:fixed; 弹窗关闭后再去掉该样式,总觉得不太对,像是打补丁。 今天终于找到了滚动穿透的原因和完...

未来cc
45分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部