Decrease Conquer

减治

减少问题规模

在广义“有序“的线性结构上搜索

反向有序：两侧性质相反

• 二分：每次减一半
• 倍增：每次扩一半，看看是否合法
• 双指针：减少组合复杂度的空间

结构有序：每次减一半

• 基于二分查找存储化的结构
  • 数组：树状数组
  • 链表：跳表
  • 树：
    • B+树
    • 线段树
    • 分块树

删除有序：每次减的不一定

• 单调栈
• 单调队列

贪心有序：减少排列和组合复杂度的空间

• 贪心法

如上的减治每一种都可以用在动规里面对动规进行优化

---

• 减一个常量，常常是减1(例如插入排序)。
• 减一个常因子，常常是减去因子2(例如折半查找)。
• 减可变规模，例如欧几里得算法).

https://blog.csdn.net/huanghanqian/article/details/79088171

减常因子算法

减常因子算法的例子有：用天平来辨别假币、俄式乘法、约瑟夫斯问题、折半查找、用平方求幂。

假币问题

在n枚外观相同的硬币中，有一枚是假币。在一架天平上，我们可以比较任意两组硬币，得知哪一组比另一组更重，但不知道重多少。假币比真币轻。要求设计算法检测这枚假币。
折半查找不是最高效的解法。

把硬币分成三堆，每堆n/3个硬币更好。
代码实现假币问题的三分算法：

减可变规模

减可变规模算法的一次迭代和另一次迭代时消减的规模是变化的。例子如：欧几里得算法、选择问题的基于分区的算法、插值查找和二叉查找树中的查找及插入操作。

计算中值和选择问题

选择问题是求一个n个数列表的第k个最小元素的问题。这个数字被称为第k个顺序统计量。
这个问题的一个更有意思的情况是在k=n/2时，它要求找出这样一个元素，该元素比列表中的一半元素大，又比另一半元素小。这个中间的值被称为中值。

中值问题的思路：先假设s是分区的分割位置。如果s=k，中轴p就是选择问题的解。如果s>k，p是s的左边区域中第k小的元素。如果s<k，p是s的右边区域中第k-s小的元素。从而减小问题规模。