1 對(duì)于分治策略中，分解容易合成較為復(fù)雜的情況，往往都需要子集有序這樣一個(gè)條件。

2 分析遞歸式的方法一般都是看主定理，主定理其實(shí)只需要記住一點(diǎn)就OK，logba.

如果不記得主定理，那么就需要分析遞歸式。

    求解遞歸式的最直接的方法是按照最初幾級(jí)的運(yùn)行時(shí)間展開遞歸式，找出當(dāng)遞歸式展開時(shí)繼續(xù)進(jìn)行的模式。然后在遞歸的所有級(jí)上求和，從而得到總的運(yùn)行時(shí)間。

    求解遞歸式的第二個(gè)方法是一開始對(duì)解有一個(gè)猜想，把它代入遞推關(guān)系，檢查其是否正確。

3 平面幾何中找最近鄰點(diǎn)對(duì)的問題，首先是對(duì)平面內(nèi)所有點(diǎn)按照x坐標(biāo)排序(很多的平面幾何問題，為了降低復(fù)雜度都需要排序，后面看到一個(gè)MIT的題目，也需要對(duì)點(diǎn)進(jìn)行極角排序)。然后分治，最后問題的關(guān)鍵是合并，取兩個(gè)子問題中的最短距離作為/theta 中間帶的衡量標(biāo)準(zhǔn)。因?yàn)橐笾虚g帶的可能的更短距離，所以所有點(diǎn)考慮的相鄰格子數(shù)有限，且每個(gè)格子只能有一個(gè)點(diǎn)。

我覺得上面那個(gè)Merge那一步是整個(gè)算法的最核心和最關(guān)鍵的地方??！

4 大整數(shù)乘法問題，給出了一個(gè)遞歸的方案。X*Y，把x分為前后兩部分，Y分為前后兩部分，交叉相乘的部分改成了一個(gè)(xh+xl)*(yh+yl)-xhyh-xlyl的過程。遞歸變成了 T(n)<= 3T(2/n)+cn .矩陣乘法問題也是類似的一個(gè)技巧。大多停留在理論階段。

下面是幾個(gè)練習(xí)題：

1 MIT的一個(gè)練習(xí)題：

平面內(nèi)給2N個(gè)點(diǎn)，無三點(diǎn)共線，分為兩類，一類是紅點(diǎn)（N個(gè)），一類是綠點(diǎn)(N個(gè))。給出一個(gè)紅點(diǎn)和綠點(diǎn)的連線方案，要求連線線段互不相交。算法復(fù)雜度O(n^2logn)

首先O(nlogn)找出分類面，分類面兩邊紅點(diǎn)綠點(diǎn)個(gè)數(shù)分別相等。方法是首先極角排序，如果極點(diǎn)是紅點(diǎn)，從小到大找到第一個(gè)綠點(diǎn)個(gè)數(shù)大于紅點(diǎn)個(gè)數(shù)的點(diǎn)。連線即為分界面。遞歸解決兩個(gè)子問題。

最壞情況是一個(gè)子問題退化為空，此時(shí)復(fù)雜度為O(n^2logn).

2 給N個(gè)數(shù)據(jù)，是一個(gè)單峰函數(shù)。O(logn)時(shí)間內(nèi)求此單峰函數(shù)的極值。

每一次探查，探查3個(gè)點(diǎn)。然后二分找。

3 求N個(gè)數(shù)的逆序?qū)栴}，只不過變形為i<j  ai>2*aj 才認(rèn)為是逆序?qū)Α＿@個(gè)問題有一個(gè)陷阱。就是要進(jìn)行兩遍Merge，第一遍是求逆序?qū)?。第二遍是排序合并?#160; 這個(gè)一定要想清楚?。?！

4 有一組N張卡，求一個(gè)方法來探測(cè)是否有大于N/2張卡等價(jià)。操作只有一種，即比較兩張卡是否等價(jià)。

5 給一個(gè)N*N的4連通網(wǎng)格圖，O(n)時(shí)間內(nèi)確定找到一個(gè)局部極小值。

思想就是先探測(cè)最外圈，然后探測(cè)次外圈，然后找中間兩條分割線，再找分成的四個(gè)小區(qū)域的最外圈?？梢哉业揭粋€(gè)局部極小值。