# 减治算法
将规模为n的问题递减为 的子问题，
反复递减后对子问题分别求解，再建立子问题的解与原问题的解的关系
分治法与减治法
关键都是：将父问题划分为子问题
区别是：分治法最后一搬需要将子问题合并求原问题的解，而减治法一般情况是：父问题的解便存在于某个子问题的解中
是一种一般性的算法设计技术，它利用了一个问题给定实例的解和同样问题较小实例的解之间的关系。一旦建立了这样一种关系，我们既可以自顶至下(递归)也可以自底至上地运用它(非递归)。
减治法有3种主要的变种：
- 减一个常量，常常是减1(例如插入排序)
n个元素我们减去C个元素（C是一个正整数） - 减一个常因子，常常是减去因子2(例如折半查找)
将集合的元素一分为二或者分成多份。比如将n-1改为n/2 - 减可变规模(例如欧几里得算法).
集合中每次减去的规模不一样,比如有n个元素的集合，我第一次减去一个元素成为n-1第二次减去了n/2的元素成为(n-1)/2.
# 对比
分治法（divide-and-conquer method）
是将一个问题划分成多个同一类型的子问题（子问题最好规模相同），之后求这些子问题的解，如果有必要的话合并（分治法一般需要合并）这些子问题的解，以得到 原始问题的答案。
分治法基础概念比较容易理解,我们可以将其理解一个树结构的处理问题方式，比如一个问题将其抽象为求n，然后分成了两个求n/2的问题，之后两个求n/2的问题又接着分形成了四个求n/4的问题，最后求得n/4的解，经过回溯得到了原本求n问题的答案。
分治和减治不同的地方是分治分开的两边都要治理，但减治减掉的那部分就不需要了。
变治法
所谓变治，就是基于"变换"的方法，首先把问题的实例变得容易求解，然后进行求解，通常，对问题的变换方式有三种：
- 实例化简：变为同样问题的一个更简单的实例；
- 改变表现：变为同样实例的不同表现；
- 问题化简：变为另一个已知算法的问题的实例
这个方法的思路类似于数学建模的思路，将生活的问题进行简单的抽象，以便对此进行研究，举一个简单的例子：
在操场（欧几里得平面）上有n>=3个人，每个人都有唯一一位最近的邻居，他们手上拿着1块奶油块，收到信号后，都会把派扔向他最近的邻居。假设n是奇数，而且每个人都可以100%命中对方，请判断对错：每次至少有一个人不会被奶油派击中。
这个问题应该是正确的，我们来以3个人A，B,C举例，假如A与B的距离为c，B与C的距离为a，C与A的距离为b，那么如果每个人都会被扔到那么他们的距离关系应当满足 ； 显然我们发现这是存在前后矛盾的因此我们可以断定每次至少有一个人不会被奶油派击中是正确的。
这是将实际问题抽象的一个例子，将人抽象成点，将距离抽象成线的长度，并且利用反证法来证明这个假设。
基于这种思想的算法也有很多，如：
- 预排序（把无序变为有序，然后处理）
- 高斯消去法（把方程组经过初等变换，得到具有特殊性质的方程组）
- 堆和堆排序（利用最大/小堆总是找到最大/小值）
# 经典运用
- 查找（折半、二叉查找树）
- 选择问题
- 插入排序
- 堆排序
- 假币问题
网友评论