知识卡片

普通读书笔记卡 · 3596.c.6.b

非均匀递归要单算叶子

理解等级:中级

对 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)。

不等高递归树尤其要区分真实叶数与包络树叶数。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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 ).