知识卡片
分治先独立求解再合并
分治把问题分解为较小部分,分别求解,再把结果组成原问题答案。原例归并排序先将支票逐层拆成小堆,之后两两有序合并,直到恢复为一堆有序结果。
拆分本身不保证结果正确,还要说明子问题如何缩小、何时能直接求解以及合并怎样保留目标性质。原文用独立子问题与动态规划作教学对比,不表示所有带递归的算法都只做独立子问题。
结构图:
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章)。 归并排序按照如下方式工作。如前所述,同样假设要排序一堆作废的支票。首先将无序的一整堆分成两