1 對(duì)于分治策略中，分解容易合成較為復(fù)雜的情況，往往都需要子集有序這樣一個(gè)條件。
2 分析遞歸式的方法一般都是看主定理，主定理其實(shí)只需要記住一點(diǎn)就OK，logba.
如果不記得主定理，那么就需要分析遞歸式。
求解遞歸式的最直接的方法是按照最初幾級(jí)的運(yùn)行時(shí)間展開(kāi)遞歸式，找出當(dāng)遞歸式展開(kāi)時(shí)繼續(xù)進(jìn)行的模式。然后在遞歸的所有級(jí)上求和，從而得到總的運(yùn)行時(shí)間。
求解遞歸式的第二個(gè)方法是一開(kāi)始對(duì)解有一個(gè)猜想，把它代入遞推關(guān)系，檢查其是否正確。
3 平面幾何中找最近鄰點(diǎn)對(duì)的問(wèn)題，首先是對(duì)平面內(nèi)所有點(diǎn)按照x坐標(biāo)排序(很多的平面幾何問(wèn)題，為了降低復(fù)雜度都需要排序，后面看到一個(gè)MIT的題目，也需要對(duì)點(diǎn)進(jìn)行極角排序)。然后分治，最后問(wèn)題的關(guān)鍵是合并，取兩個(gè)子問(wèn)題中的最短距離作為/theta 中間帶的衡量標(biāo)準(zhǔn)。因?yàn)橐笾虚g帶的可能的更短距離，所以所有點(diǎn)考慮的相鄰格子數(shù)有限，且每個(gè)格子只能有一個(gè)點(diǎn)。
我覺(jué)得上面那個(gè)Merge那一步是整個(gè)算法的最核心和最關(guān)鍵的地方！！
4 大整數(shù)乘法問(wèn)題，給出了一個(gè)遞歸的方案。X*Y，把x分為前后兩部分，Y分為前后兩部分，交叉相乘的部分改成了一個(gè)(xh+xl)*(yh+yl)-xhyh-xlyl的過(guò)程。遞歸變成了 T(n)<= 3T(2/n)+cn .矩陣乘法問(wèn)題也是類似的一個(gè)技巧。大多停留在理論階段。
下面是幾個(gè)練習(xí)題：
1 MIT的一個(gè)練習(xí)題：
平面內(nèi)給2N個(gè)點(diǎn)，無(wú)三點(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è)子問(wèn)題。
最壞情況是一個(gè)子問(wèn)題退化為空，此時(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ū)?wèn)題，只不過(guò)變形為i<j ai>2*aj 才認(rèn)為是逆序?qū)Α＿@個(gè)問(wèn)題有一個(gè)陷阱。就是要進(jìn)行兩遍Merge，第一遍是求逆序?qū)Α５诙槭桥判蚝喜ⅰ?#160; 這個(gè)一定要想清楚啊！！
4 有一組N張卡，求一個(gè)方法來(lái)探測(cè)是否有大于N/2張卡等價(jià)。操作只有一種，即比較兩張卡是否等價(jià)。
5 給一個(gè)N*N的4連通網(wǎng)格圖，O(n)時(shí)間內(nèi)確定找到一個(gè)局部極小值。
思想就是先探測(cè)最外圈，然后探測(cè)次外圈，然后找中間兩條分割線，再找分成的四個(gè)小區(qū)域的最外圈。可以找到一個(gè)局部極小值。