MAX_HEAPIFY 算法和最坏情况的递归关系
Recursive relation for the MAX_HEAPIFY algorithm and the worst case
我在经历 CLRS 时遇到了 max-heapify 算法的递归关系。我的老师证明了 max-heapify 过程的时间复杂度为 O(logn)，这实际上是非常简单的，因为最坏的情况是根必须 'bubble/float down' 从顶部一直到最后一层。这意味着我们逐层移动，因此步数等于堆的 levels/height 数，正如我们所知，它的边界是 logn。很公平。
然而，CLRS 中通过递归关系以更严格的方式证明了同样的道理。据说最坏的情况发生在最后一层半满时 has already been explained here. 所以据我从那个答案中理解，他们在数学上得出了这个结论：我们想要最大化左子树的大小 相对于堆大小n即最大化L/n的值。为了实现这一点，我们必须将最后一层填充一半，以便 L（左子树）中的节点数最大化，并且 L/n 最大化。
在最后一层添加更多的节点会增加节点的数量，但不会改变 L 的值。所以 L/n 会随着堆的增加而减少均衡。只要它是数学的，一切都很好。
现在这就是我卡住的地方：假设我在这个半填充的关卡中再添加一个节点。实际上，我看不出这是如何以某种方式减少发生的 steps/comparisons 的数量并且不再是最坏的情况。即使我多加了一个节点，所有的比较都只发生在左子树上，与右子树无关。有人能说服 me/help 我明白为什么 L/n 必须在最坏情况下最大化吗？我将不胜感激示例输入以及如何添加更多节点不再使它成为最坏的情况？
Let's say I add one more node in this half-filled level. Practically, I fail to see how this somehow reduces the number of steps/comparisons that occur and is no longer the worst case . Even though I have added one more node, all the comparisons occur only on the left subtree and has nothing to do with the right subtree.
这并没有减少步骤，这是正确的。然而，当我们谈到时间复杂度时，我们寻找的是步数与 之间的关系。如果只看步数，我们只能得出结论，最坏的情况发生在树无限大的时候。虽然那是一个非常糟糕的情况（最坏的情况），但这并不是书中“最坏情况”的意思。我们感兴趣的不仅仅是步数，还有这个数字与 .
的关系
我们可以在这里争论术语，因为通常“最坏情况”不是关于取决于的东西，而是关于 given 可能存在的变化。例如，在讨论排序算法的最坏情况时，最坏和最好的情况取决于输入数据的组织方式（已经排序、反转等）。这里“最坏情况”用于树（底层）的形状，它由 的值直接推断。一旦你拥有 ，那里就没有变化了。
然而，对于递归关系，我们必须找到公式——根据——给出左子树中子树数量的上限，其中我们希望此公式使用简单算术的约束（例如：无地板）。
这是一个图表，其中蓝色条代表 的值，橙色条代表左子树中的节点数。
递归关系是基于两个子树的最大子树是左子树的思想，所以它代表了最坏的情况。该子树的节点数介于 (-1)/2 和 2/3 之间。当左子树满时，左子树的节点数与总节点数的比值最大，而右子树的高度较小。
这里是用比率表示的相同数据：
您可以看到这些最大值出现的位置：什么时候是 2、5、11、23，... 左子树中的节点数与接近 40% 的比率。这 40% 代表该比率的 上限 ，并且是所有 .
值的安全“包罗万象”
我们在递归关系中需要这个比例：40%可以换句话说：子树中节点数的上限为2/3。所以递归关系是
() = (2/3) + O(1)
我在经历 CLRS 时遇到了 max-heapify 算法的递归关系。我的老师证明了 max-heapify 过程的时间复杂度为 O(logn)，这实际上是非常简单的，因为最坏的情况是根必须 'bubble/float down' 从顶部一直到最后一层。这意味着我们逐层移动，因此步数等于堆的 levels/height 数，正如我们所知，它的边界是 logn。很公平。
然而，CLRS 中通过递归关系以更严格的方式证明了同样的道理。据说最坏的情况发生在最后一层半满时 has already been explained here. 所以据我从那个答案中理解，他们在数学上得出了这个结论：我们想要最大化左子树的大小 相对于堆大小n即最大化L/n的值。为了实现这一点，我们必须将最后一层填充一半，以便 L（左子树）中的节点数最大化，并且 L/n 最大化。
在最后一层添加更多的节点会增加节点的数量，但不会改变 L 的值。所以 L/n 会随着堆的增加而减少均衡。只要它是数学的，一切都很好。
现在这就是我卡住的地方：假设我在这个半填充的关卡中再添加一个节点。实际上，我看不出这是如何以某种方式减少发生的 steps/comparisons 的数量并且不再是最坏的情况。即使我多加了一个节点，所有的比较都只发生在左子树上，与右子树无关。有人能说服 me/help 我明白为什么 L/n 必须在最坏情况下最大化吗？我将不胜感激示例输入以及如何添加更多节点不再使它成为最坏的情况？
Let's say I add one more node in this half-filled level. Practically, I fail to see how this somehow reduces the number of steps/comparisons that occur and is no longer the worst case . Even though I have added one more node, all the comparisons occur only on the left subtree and has nothing to do with the right subtree.
这并没有减少步骤，这是正确的。然而，当我们谈到时间复杂度时，我们寻找的是步数与 之间的关系。如果只看步数，我们只能得出结论，最坏的情况发生在树无限大的时候。虽然那是一个非常糟糕的情况（最坏的情况），但这并不是书中“最坏情况”的意思。我们感兴趣的不仅仅是步数，还有这个数字与 .
的关系我们可以在这里争论术语，因为通常“最坏情况”不是关于取决于的东西，而是关于 given 可能存在的变化。例如，在讨论排序算法的最坏情况时，最坏和最好的情况取决于输入数据的组织方式（已经排序、反转等）。这里“最坏情况”用于树（底层）的形状，它由 的值直接推断。一旦你拥有 ，那里就没有变化了。
然而，对于递归关系，我们必须找到公式——根据——给出左子树中子树数量的上限，其中我们希望此公式使用简单算术的约束（例如：无地板）。
这是一个图表，其中蓝色条代表 的值，橙色条代表左子树中的节点数。
递归关系是基于两个子树的最大子树是左子树的思想，所以它代表了最坏的情况。该子树的节点数介于 (-1)/2 和 2/3 之间。当左子树满时，左子树的节点数与总节点数的比值最大，而右子树的高度较小。
这里是用比率表示的相同数据：
您可以看到这些最大值出现的位置：什么时候是 2、5、11、23，... 左子树中的节点数与接近 40% 的比率。这 40% 代表该比率的 上限 ，并且是所有 .
值的安全“包罗万象”我们在递归关系中需要这个比例：40%可以换句话说：子树中节点数的上限为2/3。所以递归关系是
() = (2/3) + O(1)