知识卡片

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

子问题独立才方便并行

理解等级:中级

互不依赖且没有未协调共享修改的子问题,可以分配给不同执行单元,再把结果汇合。分治为并行提供结构,但不保证每个分治过程都能同时执行所有部分。

还要计调度、通信、负载不均和串行合并开销;小任务拆太细可能更慢。原书两半冒泡的n>4只是单位操作的简化演算阈值,不是实测性能边界,后续汉诺塔步骤也有顺序依赖。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      分治生成的子问题是相互独立的,因此通常可以并行解决 。也就是说,分治不仅可以降低算法的 时间复杂度,还有利于操作系统的并行优化 。 并行优化在多核或多处理器的环境中尤其有效,因为系统可以同时处理多个子问题,更加充分地利用

    参考来源

    - 位置:《Hello 算法--Go版本》第12章《分治》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/6.html;spine 5,归一字符[11820,11930)) - 结论依据:实际并行分桶/两半冒泡例及后续依赖,说明条件不把所有分治当并行。 - 原始内容:分治生成的子问题是相互独立的,因此通常可以并行解决 。也就是说,分治不仅可以降低算法的 时间复杂度,还有利于操作系统的并行优化 。 并行优化在多核或多处理器的环境中尤其有效,因为系统可以同时处理多个子问题,更加充分地利用