知识卡片
非均匀递归要单算叶子
对 T(n)=T(n/3)+T(2n/3)+Θ(n),树高 Θ(log n),每层内部成本至多 Θ(n)。
按完整二叉树上界估算叶子会过松;单列叶数递归 L(n)=L(n/3)+L(2n/3),得 O(n) 个叶子,故总上界 O(n log n)。
不等高递归树尤其要区分真实叶数与包络树叶数。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第4章 分治策略 · 查看原书依据
The cost of all leaves in the recursion tree is O(n)—asymptotically less than O(n lg n).
参考来源
- 位置:《算法导论(第4版)》第 4 章 4.4 节(`OEBPS/chapter004.xhtml`,文本字符 [50000, 55000);图 4.1–4.2、公式图 Art_P118–P128)。
- 结论依据:原文逐层汇总成本,并在非均匀树中另设叶数递归;已核对对应树图与公式图。
- 原始内容:The cost of all leaves in the recursion tree is O ( n )—asymptotically less than O ( n lg n ).