algorithm - CLRS 是否完全准确地指出 max-heapify 运行时间由重复 `T(n) = T(2n/3) + O(1)` 描述？

Question

在155页的CLRS中，关于max-heaps，max-heapify的运行时间被描述为T(n) = T(2n/3) + O(1) .

我明白为什么第一个递归调用是针对大小为 2n/3 的子问题在我们有一个几乎完整的二叉树(通常是堆的情况)的情况下，其中最深层次的节点是半满的(并且我们正在递归子树，它是包含这些最深节点的子树的根等级)。对此更深入的解释是 here .

我不明白的是:在第一次递归调用之后，子树现在是一个完整的二叉树，所以接下来的递归调用将针对大小为 n/2 的问题。

那么简单地说 max-heapify 的运行时间由递归 T(n) = T(2n/3) + O(1) 描述是否准确？ ？

Answer 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) 的结论。