一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2430|回复: 4
收起左侧

[算法题] 【LintCode, heap】为什么Heapify这题的时间复杂度是O(n)?

[复制链接] |试试Instant~ |关注本帖
小马3107 发表于 2015-8-19 22:18:47 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
题目要求和解题代码请见附件贴图。
我想请问一下大家,程序的主函数是一个for循环,调用到的siftdown函数里面是一个while循环。
为什么还可以在O(n)的时间复杂度里完成呢?

要求

要求

答案

答案
ericliu03 发表于 2015-8-20 00:06:45 | 显示全部楼层
楼主看这里:https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap

中心思想是:首先把head想做树,如果从下往上数(倒数)第h层的所有点已经是heapified的了,那么让倒数第h+1层的一个点heapify所需要的操作数最多是h步(最坏情况,最小堆里这个数是最大的,所以需要把它一层一层往下转移直到最底层)。所以对每一个h+1层的点(node)来说,复杂度O(h)。h+1层有这么多点:n/2^(k+1),所以总得复杂度就是O(h) * (n/2^(k+1)) 再对所有层数求和。最终结果就是个O(n)的。
具体公式请到wikipedia查看,注意这句:This uses the fact that the given infinite series h / 2h converges to 2.


评分

1

查看全部评分

回复 支持 3 反对 0

使用道具 举报

ericliu03 发表于 2016-7-14 06:00:08 | 显示全部楼层
何打发123 发表于 2016-7-9 10:14
你好~ 想请问一下~ 如果按照这个道理 为什么siftup就是nlogn 呢? 我觉得道理是一样的啊。。 想不明白 T T

这个siftup其实是那个straight forward的算法
每拿出来一个数放进数组(可以想象成queue)的最后,然后和他的father比较大小。
对于每个数是log(n)的时间(worst case)总共有n个数

道理确实是一样的,intuitively,不同的地方在于:假设h代表第几层,你的方法随着h增加,每层的点数也在增加,h最大的时候,也就是switch有可能最多的时候,点数是一层是2^h个点。但是lz得方法随着h的增加(倒数),每层的点数在减小,h最大的时候只有一个点。
回复 支持 1 反对 0

使用道具 举报

何打发123 发表于 2016-7-9 10:14:22 | 显示全部楼层
你好~ 想请问一下~ 如果按照这个道理 为什么siftup就是nlogn 呢? 我觉得道理是一样的啊。。 想不明白 T T Screen Shot 2016-07-08 at 10.13.06 PM.png
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-7-14 23:37:55 | 显示全部楼层
ericliu03 发表于 2016-7-14 06:00
这个siftup其实是那个straight forward的算法
每拿出来一个数放进数组(可以想象成queue)的最后,然后 ...

soga!  谢谢你的解释!虽然我没法严格的推导出来 但是有了个一个大概的意思了  感谢你啊!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 18:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表