第2章分治法（Divide & Conquer）（算法常用技术之首）六大算法常用技术：分治法（e.g. 快速排序、归并排序等）贪心法（即局部最优法，e.g. Kruscal最小生成树算法）周游法（e.g. DFS, BFS等）回朔法（e.g. 8皇后问题，平面点集的凸包等）动态规划法分枝定界法（e.g. 整数规划问题等）快速排序的思想：用O(n)的时间把一个规模为n的表分割为两段，前段中的数据元素均小于后段中的数据元素，然后对分割后所得的两个小一点的表采用同样的方法分别进行排序；当两个小表排好之后，整个表的排序也就完成了。
（思考问题：如何证明快速排序的平均时间复杂度为 (n㏒n)?提示：考虑“逆序”的个数。
）分治法的要领分治法是把一个规模较大的问题分解为若干个规模较小的子问题，这些子问题相互独立且与原问题同类；首先求出这些子问题的解，然后把这些子问题的解组合起来得到原问题的解。
由于子问题与原问题是同类的，故使用分治法很自然地要用到递归。
因此分治法分三步：1 将原问题分解为子问题（Divide）2 求解子问题（Conquer）3 组合子问题的解得到原问题的解（Combine）分治法举例：给定n个数据元素，要找出其中的最大元和最小元。
简单直观的方法：一个一个地找，用n-1次比较来找出最大元，再用n-2次比较来找出最小元。
比较次数（基本运算）为2n-3次。
用分治法如何求解？当n=2时，一次比较就可以找出两个数据元素的最大元和最小元。
当n>2时，可以把n个数据元素分为大致相等的两半，一半有⎣n/2⎦个数据元素，而另一半有⎡n/2⎤个数据元素。
先分别找出各自组中的最大元和最小元，然后将两个最大元进行比较，就可得n个元素的最大元；将两个最小元进行比较，就可得n个元素的最小元。
因此算法的时间复杂度为：T(n)=⎩⎨⎧>+=22)2/(221n n T n 此方程可用主定理求解：a=2, b=2, f(n)=2, a Log b n =n 1, f(n)比a Log b n 的量级低（第一种情况）；所以可得T(n)= Θ(a Log b n)= Θ(n)。
