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)時間內確定找到一個局部極小值。

思想就是先探測最外圈，然后探測次外圈，然后找中間兩條分割線，再找分成的四個小區域的最外圈。可以找到一個局部極小值。