CLRS 是否完全准确地指出 max-heapify 运行 时间由递归“T(n) = T(2n/3) + O(1)”描述？
Is CLRS completely accurate to state that max-heapify running time is described by the recurrence `T(n) = T(2n/3) + O(1)`?
在第155页的CLRS中，关于max-heaps，max-heapify的运行时间被描述为T(n) = T(2n/3) + O(1)。
我理解为什么第一次递归调用是在大小为 2n/3 的子问题上，在我们有一个几乎完整的二叉树（通常是堆的情况）的情况下，其中最深层次的节点是一半full（并且我们在子树上递归，该子树是在最深层次上包含这些节点的子树的根）。更深入的解释是 here.
我不明白的是：在第一次递归调用之后，子树现在是一个完整的二叉树，所以接下来的递归调用将针对大小 n/2.
的问题
那么简单地说 max-heapify 的 运行 时间由递归 T(n) = T(2n/3) + O(1) 描述是否准确？
将我的评论转换为答案：如果假设 T(n)（构建具有 n 个节点的最大堆所需的时间）是 n 的非递减函数，那么我们知道 T(m) ≤ T(n) 对于任何 m ≤ n。你是正确的，2n / 3 的比率是最坏情况的比率，并且在第一级递归之后它不会达到，但在上述假设下你可以安全地得出 T(n / 2) ≤ T(2n / 3)，所以我们可以将递归上限设为
T(n) ≤ T(2n / 3) + O(1)
即使严格相等不成立。然后让我们使用主定理得出结论 T(n) = O(log n).
在第155页的CLRS中，关于max-heaps，max-heapify的运行时间被描述为T(n) = T(2n/3) + O(1)。
我理解为什么第一次递归调用是在大小为 2n/3 的子问题上，在我们有一个几乎完整的二叉树（通常是堆的情况）的情况下，其中最深层次的节点是一半full（并且我们在子树上递归，该子树是在最深层次上包含这些节点的子树的根）。更深入的解释是 here.
我不明白的是：在第一次递归调用之后，子树现在是一个完整的二叉树，所以接下来的递归调用将针对大小 n/2.
的问题那么简单地说 max-heapify 的 运行 时间由递归 T(n) = T(2n/3) + O(1) 描述是否准确？
将我的评论转换为答案：如果假设 T(n)（构建具有 n 个节点的最大堆所需的时间）是 n 的非递减函数，那么我们知道 T(m) ≤ T(n) 对于任何 m ≤ n。你是正确的，2n / 3 的比率是最坏情况的比率，并且在第一级递归之后它不会达到，但在上述假设下你可以安全地得出 T(n / 2) ≤ T(2n / 3)，所以我们可以将递归上限设为
T(n) ≤ T(2n / 3) + O(1)
即使严格相等不成立。然后让我们使用主定理得出结论 T(n) = O(log n).