创建最大堆 O(n) 的时间复杂度如何。是子节点仅在 O(i) 中与其父节点进行比较还是 O(log n)。
问问题
1316 次
1 回答
1
一个。如果我们使用冒泡方法进行排序，复杂度是 O(n)。
这里的想法是堆是通过盲目地将元素插入到数组中来构建的，然后使用自下而上的方法开始纠正/交换优势违规。优点：我们有 n/2 个叶子节点，它们不需要任何气泡，因为它们会自动服从优势。然后我们转向内部父母并将其与它的孩子进行比较。如果存在违规行为，则交换/冒泡。然后移动到更高的父级，依此类推即使内部（父级）节点也需要根据它们所在级别的高度进行交换。n / 2是叶子。n/4 的高度为 1，n/8 的高度为 2...导致构建堆的成本为以下等式。（最大高度：lg n）
从 0 到 lg n 的总和：(n/2^h+1)h
归结为大约。2n
因此时间复杂度为 O(n)。
湾。比较只发生在给定父级的子级上。
希望它回答了你的问题
于 2013-10-07T04:34:40.433 回答