分治算法的基本知识记录
分治算法的全称应该是分而治之（ divide and conquer， D&C）
一、概念
1、简单定义
分治算法的核心思想是将原问题划分成规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
2、性质
D&C并非可用于解决问题的算法，而是一种解决问题的思路。
3、基本要求
根据D&C的定义，每次递归调用都必须缩小问题的规模。
二、步骤
使用D&C解决问题的过程最重要的是两个步骤。
(1) 找出基线条件，这种条件必须尽可能简单。
(2) 不断将问题分解（或者说缩小规模），直到符合基线条件。
最后将问题递归解决，并合并出最终的解
三、核心思路
与核心思路相对应的，分治思想核心思路也是两条
1、 找出简单的基线条件；
2、 确定如何缩小问题的规模，使其符合基线条件。
基线条件的定义参见递归算法的相关概念
四、使用条件
使用D&C解决问题，往往需要满足以下条件，才能实现或充分发挥D&C的优越性
1、问题的规模缩小到一定的程度 可以直接求解
2、问题可以分解为若干个规模较小的相同问题，即该问题具有 最优子结构性质
3、利用分解出的子问题的解 可以合并为问题的解
4、分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题
原文地址：https://blog.csdn.net/well_fly/article/details/143063300
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！