# 分治法小记

将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。

递归地解这些问题，然后将各个子问题的解合并在一起，从而得到原问题的解。

# 分治法的基本框架

规模很小的时候直接求解，如果规模较大，就将其分为k个子问题，用递归分别去解。

# 二分搜索有序表

二分搜索有序表，每次循环查找区间减半，查找区间构成一颗二叉树，最坏的情况是一直走到二叉树的叶子节点。因此算法的复杂度为log n + 1。

# 分治法的时间复杂性

子问题的复杂性当然低于原问题。但是整体上能否降低复杂性还取决于合并。通过降低合并的复杂性，可以降低原问题求解的复杂性。

有时候如果没有更好的方法的话，可以使用一些计算上的小技巧来处理降低时间复杂度。