分治法

分治法要素

1. 原问题可以分解为若干个规模较小的子问题。
2. 子问题相互独立。
3. 子问题的解可以合并为原问题的解。

分治法的步骤

1. 分解：将要解决的问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
2. 治理：求解各个子问题。由于各个子问题与原问题形式相同，只是规模较小而已，而当子问题划分的足够小时，就可以用较简单的方法解决。
3. 合并：按原问题的要求，将子问题的解逐层合并构成原问题的解。

一言以蔽之，分治法就是将一个 难以解决的大问题，分割成一些规模较小的相同问题，以便逐个击破，分而治之。

二分查找

关于二分查找的具体思路和实现就再作介绍了，就简单算一下为什么二分查找的时间复杂度为O(logn)，不包括排序步骤。

1. 当n=1时，需要一次比较，T(n)=O(1)。
2. 当n>1时，特定元素和中间元素比较，需要O(1)时间，如果比较不成功，则需要在前半部分或后半部分搜索，问题的规模缩小了一半，时间复杂度变成了T(n/2)。有T(n)=T(n/2)+O(1), n>1; T(n)=O(1), n=1。
3. 当n>1时，可以递推求解如下。

    T(n) = T(n/2) + O(1)
         = T(n/2^2) + 2O(1)
         = T(n/2^3) + 3O(1)
         ......
         = T(n/2^x) + xO(1)

递推最终的规模为1，令n=2^x，则x=logn。

    T(n) = T(1) + logn * O(1)
         = O(1) + logn * O(1)
         = O(logn)

由此可知二分查找的时间复杂度为O(logn)。

4. 空间复杂度：程序中的变量占用了一些辅助空间，这些辅助空间都是常数级的，因此空间复杂度为O(1)。但是如果采用递归方式实现的话，空间复杂度就是O(logn)。