用 Big-oh 操作方程

笔记: 第一部分是关注下面标记为“问题”的所有上下文:

与 CLRS 合作算法简介 ,第 3 版,在第 6.4 章中,因为他们正在讨论他们指定的堆:

对 MAX - HEAPIFY 的每个电话呼叫都会花费 $O(lg\ n)$ 并且 BUILD - MAX - HEAP 会进行 $O(n)$ 个这样的呼叫。

好的,我和他们在一起,BUILD - MAX - HEAP 的运行时间因此是 $O(n\ lg\ n)$,他们接着说:

这个上限虽然是正确的,但并不是渐近严格的。

我也理解这一点,因为真正的 MAX - HEAPIFY 每次调用时都不会在 $lg\ n$ 度上运行,而是在 $h$ 度上运行,其中 h 是它被调用的节点的高度。 所以他们指定:

我们更严格的分析依赖于 $n$ - 方面堆具有高度 $\lfloor lg\ n \rfloor$ 以及任何高度 $h$ 的大多数 $\lceil n/2^{h+1}\rceil$ 节点的住宅或商业属性。

好的,我知道整个树仍然有大小为 $n$ 的节点,当海拔 = 0:$n/2^0 = n$ 时,它确实使用了该公式。

MAX - HEAPIFY 在联系海拔 h 的节点时所需的时间是 $O(h)$,因此我们可以分摊 BUILD - MAX - HEAP 的总费用,从上面限定为:

$\displaystyle\sum_{h=1}^{\lceil lg\ n\rceil} \lceil {\frac{n}{2^{h+1}}} \rceil O(h) = O(n\displaystyle\sum_{h=1}^{\lceil lg\ n\rceil} {\frac{h}{2^{h}}})$

问题

这就是我要摆脱的地方,我不明白 $^{+1}$ 是如何在 $2^{h+1}$ 上消失的。 当您将公式放入 Big 中时,是否可以做出某种不成文的假设 - 哦? 还是因为他们取消了天花板功能?

3
2022-06-07 14:39:19
资源 分享
答案: 1

$O(2^{n+1})=O(2\cdot 2^n)=O(2^n)$ 假设对于任何类型的函数 $f(n)$ 和常数 $C>0$,我们都有 $O(C\cdot f(n))=O(f(n))$。

4
2022-06-07 15:06:32
资源