如何推导Heapify算法的最坏情况时间复杂度？
How to derive the worst case time complexity of Heapify algorithm?
我想知道如何推导堆数据结构的 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是子树中元素的总数子树。
这是一个变量替换。
首先，认识到在等式的最左边，和的最后一项为零（因为当i = k、k-i = 0）。所以，第一次求和的范围可以写成1 <= i <= k-1。现在，将 i 替换为 k-i。 i迭代集合{1, 2, ... , k-1}和k-i迭代集合{k-1, ... 2, 1}，它们是同一个集合，因此，我们可以做这个替换。
我想知道如何推导堆数据结构的 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是子树中元素的总数子树。
这是一个变量替换。
首先，认识到在等式的最左边，和的最后一项为零（因为当i = k、k-i = 0）。所以，第一次求和的范围可以写成1 <= i <= k-1。现在，将 i 替换为 k-i。 i迭代集合{1, 2, ... , k-1}和k-i迭代集合{k-1, ... 2, 1}，它们是同一个集合，因此，我们可以做这个替换。