当前位置:   article > 正文

构建堆的时间复杂度_二叉堆建堆时间复杂度

二叉堆建堆时间复杂度

大顶堆、小顶堆是一种很常用的数据结构,例如常见的堆排序和topk算法,在很多应用场景中,我们经常会关注算法时间复杂度和空间复杂度,众所周知构建堆的时间复杂度是o(n),那么为什么是o(n)?本文主要跟大家讨论下这个问题。

堆是一颗完全二叉树,假设有n个节点,树高这里写图片描述

证明方法如下:
1. 假设根节点的高度为0,叶子节点高度为h,那么每层包含的元素个数为2^x,x从0到h。
2. 构建堆的过程是自下而上,对于每层非叶子节点需要调整的次数为h-x,因此很明显根节点需要调整(h-0)次,第一层节点需要调整(h-1)次,最下层非叶子节点需要调整1次。
3. 因此可知,构造树高为h的二叉堆精确时间复杂度为:
s = 1*2^(h-1) + 2*2^(h-2)+……+h*2^0

可以看出以上公式是等差数列和等比数列乘积之和,可以通过错位相减求:
2s = 2^h + 2*2^(h-1)+3*2^(h-2)+……+h*2^1

因此可得:
s = 2s -s = 2^h + 2^(h-1) + 2^(h-2) +…… + 2^1 - h

最终可以通过等比数列公式进行计算得到s = 2*2^h - 2 -h
这里写图片描述代入的s = 2n - 2 - log2(n),近似的时间复杂度就是O(n)。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/空白诗007/article/detail/838316
推荐阅读
相关标签
  

闽ICP备14008679号