知识卡片

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

分治先证明可分和可合

理解等级:中级

分治把原问题拆成更小的同类子问题,求出后再合成原解。适用前应说明子问题如何覆盖原任务、它们之间是否独立,以及结果怎样合并。

拆分本身不保证更快,分解与合并可能抵消收益。只递归处理一个确定子问题的二分可以不做结果合并,复杂度仍应按真实工作计算;把数组一分为二也可能只传边界而无需复制全部元素。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      问题可以分解 :原问题可以分解成规模更小、类似的子问题,以及能够以相同方式递归地进行划分。 2. 子问题是独立的 :子问题之间没有重叠,互不依赖,可以独立解决。 3. 子问题的解可以合并 :原问题的解通过合并子问题的解得

    参考来源

    - 位置:《Hello 算法--Go版本》第12章《分治》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/6.html;spine 5,归一字符[10804,10914)) - 结论依据:实际三条件与二分/归并两种流程,限定划分/合并成本。 - 原始内容:问题可以分解 :原问题可以分解成规模更小、类似的子问题,以及能够以相同方式递归地进行划分。 2. 子问题是独立的 :子问题之间没有重叠,互不依赖,可以独立解决。 3. 子问题的解可以合并 :原问题的解通过合并子问题的解得