知识卡片
建堆总成本为线性
把 n 次堆化都按最坏树高 O(log n) 估算会得到宽松的 O(n log n)。
实际上高度 h 的节点至多约 n/2^(h+1),每个只需 O(h),总和 O(n Σh/2^h)=O(n)。大多数节点靠近叶子,代价很低。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 建堆总成本为线性
原书出处 · 1 处
- 第6章 堆排序 · 查看原书依据
Hence, we can build a max-heap from an unordered array in linear time.
参考来源
- 位置:《算法导论(第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.