澄清$ \ sum_ {h= 0} ^ {\ lfloor lg（n）\ rfloor} \ lceil \ frac {n} {2 ^ {h + 1}} \ rceil o（h）= o（n \ sum_ {h= 0} ^ {\ lfloor lg（n）\ rfloor} \ frac {h} {2 ^ h}）$ in build-max-heap

Question

我正在通过cormen等进行文本介绍算法。 al。在分析 $ build-max-heap $ 程序的时间复杂性的情况下，我遇到了一个步骤。

程序如下：

BUILD-MAX-HEAP(A)
1   heap-size[A] <- length[A]
2   for i <- ⌊length[A]/2⌋ downto 1
3       MAX-HEAPIFY(A,i)

. 现在，作者声称通过观察 $ max-heapify $ 在节点上运行的时间随着节点的高度而变化的时间树，大多数节点的高度很小。更严格的分析依赖于 $ n $ -element堆的属性堆积高度 $ \ lfloor lg（n）\ rfloor $ ，最多 $ \ lceil \ frac {n} {2 ^ {h + 1}} \ rceil $ 任何高度 $ H $ 。

so， $$ \ sum_ {h= 0} ^ {\ lfloor lg（n）\ rfloor} \ lceil \ frac {n} {2 ^ {h + 1} } \ rceil o（h）= o（n \ sum_ {h= 0} ^ {\ lfloor lg（n）\ rfloor} \ frac {h} {2 ^ h}）\ ldots \ tag1 $$

现在它在上面的步骤中，我面临的问题。 作者如何使用LHS在RHS上获得表达式，如此简单地（仿佛直观）。但是我似乎没有共享相同的直觉。

现在，任何节点的最大高度是root的高度是 $ \ lfloor lg（n）\ rfloor $ 。现在，让我们找到Fraction $ \ frac {n} {2 ^ {h + 1}} $ 的最小可能值的绑定。 class=“math-container”> $ h=lfloor lg（n）\ rfloor $

so， $$ \ frac {n} {2 ^ {\ lfloor lg（n）\ rfloor + 1}}=frac {n} {2.2 ^ {\ lfloor lg（n）\ rfloor}} \ geqslant \ frac {n} {2.2 ^ {lg（n）}}=frac {n} {2n}=frac {1} {2} \ ldots \ tag 2 $$

现在来自作者的分析步骤（1），他们假设

$$ \ lceil \ frac {n} {2 ^ {h + 1}} \ rceil \ leqslant c。\ frac {n} {2 ^ h}，c> 0 $$

现在我从数学中知道，

$$ \ lceil \ frac {n} {2 ^ {h + 1}} \ rceil \ lt \ frac {n} {2 ^ {h + 1}} + 1 $$

而且作者效果的方式，它必须是如下所示，

$$ \ lceil \ frac {n} {2 ^ {h + 1}} \ rceil \ lt \ frac {n} {2 ^ {h + 1}} + 1 \ leqslant c。\ frac {n} $$

so， $$ \ frac {n} {2 ^ {h + 1}} + 1 \ leqslant c. \ frac {n} {2 ^ {h}} $ $

$$ \ iff 1 \ leqslant c. \ frac {n} {2 ^ {h}} - \ frac {n} {2 ^ {h + 1}} $ $

$$ \ iff 1 \ leqslant \ frac {n} {2 ^ {h + 1}}（2c-1）$$

$$ \ iff \ frac {n} {2 ^ {h + 1}} \ geqslant \ frac {1} {2c-1} \ ldots \ tag 3 $$

现在（3）遵守（2）我们应该，

$$ 2.C-1 \ GEQSLANT 2 \ IFF C \ GEQSLANT \ FRAC {3} {2} $$

现在是（1）中的单线值得这么大的努力，或者是我们可以在精神上做这一步骤的阶段琐碎或直观的情况。如果是后者，请用这种直觉启发我。

即使在此答案中 $ \ frac {n {2 ^ {h + 1}} \ lt \ frac {n} {2 ^ {h}} $ 是直观的，但 $ 1 \ lt \ frac {n {2 ^ {h}} $ 不是非常直观的，需要使用（2）我觉得

Answer 1

自 $ h \ leq \ lfloor \ lg n \ rfloor $ ，我们有 $ 2 ^ h \ leq n $，so $ n / 2 ^ {h + 1} \ geq 1/2 $ 。所以 $$ \左\ lceil \ frac {n} {2 ^ {h + 1}} \ \ \ rceil \ leq \ frac {n} {2 ^ {h + 1}} + 1= \ frac {n} {2 ^ {h + 1}} + 2 \ cdot \ frac {1} {2} \ leq \ frac {n} {2 ^ {h + 1}} + 2 \ frac {n} {2 ^ {h + 1}}= 3 \ frac {n} {2 ^ {h + 1}}。 $$ （实际上，如果您更小心，那么您可以替换 $ 3 $ by $ 2 $ 。）

更一般地，如果 $ x \ geq c> 0 $ 那么 $ \ lceil x \ rceil= o（x）$ ，其中隐藏常量取决于 $ c $ 。