1 对于分治策略中，分解容易合成较为复杂的情况，往往都需要子集有序这样一个条件。
2 分析递归式的方法一般都是看主定理，主定理其实只需要记住一点就OK，logba.
如果不记得主定理，那么就需要分析递归式。
求解递归式的最直接的方法是按照最初几级的运行时间展开递归式，找出当递归式展开时继续进行的模式。然后在递归的所有级上求和，从而得到总的运行时间。
求解递归式的第二个方法是一开始对解有一个猜想，把它代入递推关系，检查其是否正确。
3 平面几何中找最近邻点对的问题，首先是对平面内所有点按照x坐标排序(很多的平面几何问题，为了降低复杂度都需要排序，后面看到一个MIT的题目，也需要对点进行极角排序)。然后分治，最后问题的关键是合并，取两个子问题中的最短距离作为/theta 中间带的衡量标准。因为要求中间带的可能的更短距离，所以所有点考虑的相邻格子数有限，且每个格子只能有一个点。
我觉得上面那个Merge那一步是整个算法的最核心和最关键的地方！！
4 大整数乘法问题，给出了一个递归的方案。X*Y，把x分为前后两部分，Y分为前后两部分，交叉相乘的部分改成了一个(xh+xl)*(yh+yl)-xhyh-xlyl的过程。递归变成了 T(n)<= 3T(2/n)+cn .矩阵乘法问题也是类似的一个技巧。大多停留在理论阶段。
下面是几个练习题：
1 MIT的一个练习题：
平面内给2N个点，无三点共线，分为两类，一类是红点（N个），一类是绿点(N个)。给出一个红点和绿点的连线方案，要求连线线段互不相交。算法复杂度O(n^2logn)
首先O(nlogn)找出分类面，分类面两边红点绿点个数分别相等。方法是首先极角排序，如果极点是红点，从小到大找到第一个绿点个数大于红点个数的点。连线即为分界面。递归解决两个子问题。
最坏情况是一个子问题退化为空，此时复杂度为O(n^2logn).
2 给N个数据，是一个单峰函数。O(logn)时间内求此单峰函数的极值。
每一次探查，探查3个点。然后二分找。
3 求N个数的逆序对问题，只不过变形为i<j ai>2*aj 才认为是逆序对。这个问题有一个陷阱。就是要进行两遍Merge，第一遍是求逆序对。第二遍是排序合并。 这个一定要想清楚啊！！
4 有一组N张卡，求一个方法来探测是否有大于N/2张卡等价。操作只有一种，即比较两张卡是否等价。
5 给一个N*N的4连通网格图，O(n)时间内确定找到一个局部极小值。
思想就是先探测最外圈，然后探测次外圈，然后找中间两条分割线，再找分成的四个小区域的最外圈。可以找到一个局部极小值。