知识卡片

普通读书笔记卡 · 5654.c.3.b

调用树展示重复子问题

理解等级:中级

一个调用产生多个子调用时,可以把调用关系画成树,按层观察规模、分支数和重复状态。朴素斐波那契每层计算前两个编号,许多相同编号会在不同分支重复求值。

调用树帮助分析总工作,最大路径深度帮助分析调用栈,两者不能混算。看到重复子问题提供后续缓存的动机,不表示所有递归都必然指数增长。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      从一个调用产生了两个调用分支。如图2‑6 所 示,这样不断递归调用下去,最终将产生一棵层数为 的「递归树recursion tree」 。 图2‑6 斐波那契数列的递归树 从本质上看,递归体现了“将问题分解为更小子问题”

    参考来源

    - 位置:《Hello 算法--Go版本》第02章《复杂度分析》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/1.html;spine 0,归一字符[22607,22717)) - 结论依据:实际fib代码和树图展示分支与相同状态重复,区分树节点总数及深度。 - 原始内容:从一个调用产生了两个调用分支。如图2‑6 所 示,这样不断递归调用下去,最终将产生一棵层数为 的「递归树recursion tree」 。 图2‑6 斐波那契数列的递归树 从本质上看,递归体现了“将问题分解为更小子问题”