第二章分治法( Divide and Conquer) “分”而治之 2.1一般方法 对大规模问题的求解 利用分治法求解大规模问题 子问题 问题求解 1.分治策略基本思想 当问题的规模较大。叫 结果 而无法直接求解时,将分 合并 整个问题分成若干个小 问题,然后分而治之。 可用递归过程描述, 一般情况下,子问题与原始问题“同质第二章 分治法（Divide and Conquer) —— “分”而治之 2.1 一般方法 ◼ 对大规模问题的求解 ◼ 利用分治法求解大规模问题 Q q2 qk q1 子问题 ... a2 ak a1 子问题求解 ... 问题 A 子结果 分解 合并 逐步细化的过程 1.分治策略基本思想 当问题的规模较大 而无法直接求解时，将 整个问题分成若干个小 问题，然后分而治之。 可用递归过程描述。 一般情况下，子问题与原始问题“同质