知识卡片

普通读书笔记卡 · 3623.c.2

子问题图揭示计算规模

理解等级:高级

子问题图以每个不同状态为顶点、直接依赖为有向边,可视为把递归树中重复状态折叠合并。自底向上须按依赖的反向拓扑顺序计算;若处理一个状态的成本与出边数成正比,总成本通常随顶点加边数增长。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 14 章 14.1 节(`OEBPS/chapter014.xhtml`,文本字符 [15000, 25000);图 14.4、Art_P455)。 - 结论依据:子问题图定义为每个不同状态一个顶点、直接依赖一条有向边;原文说明自底向上按反向拓扑顺序,若每态工作与出边成正比,总成本与图规模相关。 - 原始内容:It is a directed graph, containing one vertex for each distinct subproblem.