知识卡片

普通读书笔记卡 · 3613.a.1.a.1

建堆总成本为线性

理解等级:中级

把 n 次堆化都按最坏树高 O(log n) 估算会得到宽松的 O(n log n)。

实际上高度 h 的节点至多约 n/2^(h+1),每个只需 O(h),总和 O(n Σh/2^h)=O(n)。大多数节点靠近叶子,代价很低。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 6 章(`OEBPS/chapter006.xhtml`,文本字符 [10000, 15000);图 6.1–6.4 与公式图 Art_P298–P304)。 - 结论依据:6.3 节按节点高度 h 计费:Art_P302–P303 将至多 ⌈n/2^(h+1)⌉ 个节点各自 O(h) 求和,并以 Σh/2^h 收敛推出 O(n)。 - 原始内容:Hence, we can build a max-heap from an unordered array in linear time.