Divide and Conquer - 分治

把原始问题分解为若干子问题，在逐个解决各个子问题的基础上，得到原始问题的解。 经常和递归联系在一起。因此如果计算时间复杂度，其递推公式很重要。

几个常见的使用分治的问题

• FindMaxMin

n个整数元素的数组A[1… n], n 为2的幂， 传统算法的比较次数为2n-2，采用分治得到的公式为 C(n) = 1 n=2； C(n) = 2C(n/2)+2 n > 2 根据递推公式可以得到其比较的次数为 3/2n-2，相对传统算法得到了提升。

• 二分查找

在已经排序的数组上进行二分查找，其时间复杂度了log(n)。其递推公式为(n) = 1 n=1 ； C(n) = C(n/2)+1 n>1

• 合并排序

思路很简单，将待排序数组对半分成两个子数组；分别对两个子数组排序；将两个已排序的子数组合并。给出最大笔记次数和最小比较次数的递推公式。
C(n) = 0 n=1 ；C(n) = 2C(n/2)+n-1 n>1 || C(n) = 0 n=1 ; C(n) = 2C(n/2)+n/2 n>1

• 寻找第K小的元素

  比较朴素的做法有，直接查找，找到第1小，然后找第2小。。一直到第k小，时间复杂度应该是 kn，如果k接近 n/2，那么复杂度为 n*n/2.第二种比较朴素的做法进行排序，nlog(n)的复杂度。在分治的算法中有一个办法，比较复杂，就直接贴算法的照片了。

  除了分治之外，还有减治和变治

  减治：每次算法迭代总是从实例规模中减去一个规模相同的常量。经常地，这个常量等于一。