algorithm - 如何推导出 Heapify 算法的最坏情况时间复杂度？

Question

我想知道如何推导出堆数据结构的 Heapify 算法的时间复杂度。

我是根据 Ellis Horowits 的《计算机算法基础》一书提出这个问题的。我正在添加一些算法的屏幕截图以及书中给出的推导。

算法：

最坏情况复杂度的推导：

我理解了这个计算的第一部分和最后一部分，但我不知道如何2^(i-1) x (k-i)变成i2^(k-i-1).

我在互联网上可以找到的所有推导都采用不同的方法，通过不同地考虑树的高度。我知道这种方法也会导致相同的答案，但我想知道这种方法。

您可能需要以下信息：

2^k-1 = n或近似2^k = n，其中 k 是级别数，从根节点开始，根级别为 1（不是 0），n 是节点数。

此外，函数的最坏情况时间复杂度与Adjust()它被调用的子树的高度成正比，即 O(log n，其中 n 是子树中元素的总数。

标签： algorithmmathtime-complexityheapheapsort

Answer 1

这是一个变量替换。

首先，意识到在等式的最左边，和的最后一项为零（因为当i = k, k-i = 0）。所以，第一次求和的范围可以写成1 <= i <= k-1。现在，替换i为k-i. i迭代集合{1, 2, ... , k-1}和k-i迭代集合{k-1, ... 2, 1}，它们是同一个集合，因此，我们可以做这个替换。