知识卡片

结构图卡 · 1292.g.1.e · 生成模型:未记录

分治先独立求解再合并

理解等级:中级

分治把问题分解为较小部分,分别求解,再把结果组成原问题答案。原例归并排序先将支票逐层拆成小堆,之后两两有序合并,直到恢复为一堆有序结果。

拆分本身不保证结果正确,还要说明子问题如何缩小、何时能直接求解以及合并怎样保留目标性质。原文用独立子问题与动态规划作教学对比,不表示所有带递归的算法都只做独立子问题。

结构图:

flowchart TD
 A[分解成更小部分] --> B[分别求解各部分]
 B --> C[按目标性质合并]
 C --> D[得到当前问题结果]
这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      分治法包含3个步骤:分解、求解与合并。在分解阶段,将数据分解为更小、更容易管理的部分。在求解阶段,对每个分解出的部分进行处理。在合并阶段,将每部分处理的结果进行合并。一个分治法的例子是归并排序(见第12章)。 归并排序按照如下方式工作。如前所述,同样假设要排序一堆作废的支票。首先将无序的一整堆分成两

    参考来源

    - 位置:《算法精解:C语言描述》第1章《算法设计的一般方法》(spine1180;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1148.html;u016-ch01-006)。 - 结论依据:16分治段明确分解/求解/合并三步骤,并以归并支票反复拆分及有序合并说明;流程图只重组这三个阶段。 - 原始内容:分治法包含3个步骤:分解、求解与合并。在分解阶段,将数据分解为更小、更容易管理的部分。在求解阶段,对每个分解出的部分进行处理。在合并阶段,将每部分处理的结果进行合并。一个分治法的例子是归并排序(见第12章)。 归并排序按照如下方式工作。如前所述,同样假设要排序一堆作废的支票。首先将无序的一整堆分成两