知识卡片
分治先证明可分和可合
分治把原问题拆成更小的同类子问题,求出后再合成原解。适用前应说明子问题如何覆盖原任务、它们之间是否独立,以及结果怎样合并。
拆分本身不保证更快,分解与合并可能抵消收益。只递归处理一个确定子问题的二分可以不做结果合并,复杂度仍应按真实工作计算;把数组一分为二也可能只传边界而无需复制全部元素。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
问题可以分解 :原问题可以分解成规模更小、类似的子问题,以及能够以相同方式递归地进行划分。 2. 子问题是独立的 :子问题之间没有重叠,互不依赖,可以独立解决。 3. 子问题的解可以合并 :原问题的解通过合并子问题的解得
参考来源
- 位置:《Hello 算法--Go版本》第12章《分治》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/6.html;spine 5,归一字符[10804,10914))
- 结论依据:实际三条件与二分/归并两种流程,限定划分/合并成本。
- 原始内容:问题可以分解 :原问题可以分解成规模更小、类似的子问题,以及能够以相同方式递归地进行划分。 2. 子问题是独立的 :子问题之间没有重叠,互不依赖,可以独立解决。 3. 子问题的解可以合并 :原问题的解通过合并子问题的解得