中图种学学计算机科学与术系 University of Science and Technology of China DEPARTMENT。 F COMPUTE三巴 ENCE AND ECHNOLDD 分治策略( Divide and Conquer) ■其基本思想是将一个大而复杂 原问题 的问题分解成若干个特性相同 的子问题分而治之。若所得的 子问题规模仍嫌过大,则可反 复使用分治策略,直至很容易分归 求解诪子问題为止。问题求解解井 可分为三步:①将輪入分解成 若千个想近于相子的子问题;O 子问题 ②同时递归地求解诸子问题; ③归并各子问题的解成为原问 分解过程 归并过程 题的解。 国家高性能计算中心(合肥) 2021/2/1 13国家高性能计算中心（合肥） 13 2021/2/1 分治策略（Divide and Conquer） ▪ 其基本思想是将一个大而复杂 的问题分解成若干个特性相同 的子问题分而治之。若所得的 子问题规模仍嫌过大，则可反 复使用分治策略，直至很容易 求解诸子问题为止。问题求解 可分为三步：①将输入分解成 若干个规模近于相等的子问题； ②同时递归地求解诸子问题； ③归并各子问题的解成为原问 题的解。 原问题 子问题 分 解 归并 分解 归 并 分解过程 归并过程