构建堆的时间复杂度

如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。考虑以下用于构建输入数组 A 的堆的算法。C语言 从数组构建堆https://blog.csdn.net/hefeng_aspnet/article/details/160408143C 从数组构建堆https://blog.csdn.net/hefeng_aspnet/article/details/160407485C# 从数组构建堆https://blog.csdn.net/hefeng_aspnet/article/details/160408252Java 从数组构建堆https://blog.csdn.net/hefeng_aspnet/article/details/160408186JavaScript 从数组构建堆https://blog.csdn.net/hefeng_aspnet/article/details/160408286Python 从数组构建堆https://blog.csdn.net/hefeng_aspnet/article/details/160408221快速浏览上述实现可知运行时间为O(n∗lg(n))因为每次调用Heapify都会产生费用O(lg(n))并且构建堆O(n)这样的电话。这个上限虽然正确但并非渐近紧致。我们可以通过观察以下事实推导出更紧的界限 Heapify的运行时间取决于树的高度 h等于 log n其中 n 为节点数而大多数子树的高度都很小。高度 h 会随着我们沿着树向上移动而增加。Build-Heap的第 3 行执行一个循环从最后一个内部节点堆大小/2高度为 1的索引处开始循环到根节点1高度为 lg(n)的索引处。因此Heapify对每个节点的运行时间都不同具体如下为了计算构建堆的时间复杂度我们必须知道高度为 h 的节点数。为此我们利用以下事实大小为 n 的堆最多有 O(n^2) 个节点。高度为 h 的节点。为了推导出时间复杂度我们将构建堆的总成本表示为步骤 2 利用大 O 符号的性质忽略向上取整函数和常数类似地在步骤三中由于我们使用了大O符号求和的上限可以增加到无穷大。无穷等比数列 (x 1) 的和​两边同时求导并乘以 x我们得到​将式 (3) 中得到的结果代入推导式 (1)我们得到​​因此构建二叉堆的时间复杂度为O(n)。如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。