馬上就要算法考試了饶囚，好緊張，先復(fù)習第一波....
參考文獻（算法導(dǎo)論）+（張莉老師ppt）
函數(shù)的增長鸠补，對算法效率的描述
漸進記號：Θ萝风、Ω、O紫岩、o规惰、w(那個很像w的符號，不記得咋打出來了)
Θ標記（最常用）：存在正常量c1和c2泉蝌，使得當n 足夠大的時候歇万，能夠讓函數(shù) f(n) 夾入c1g(n)和c2g(n)之間
如圖：
稱g(n)是f(n）的一個漸進緊確界，也就是f(n）得在c1g(n)和c2g(n)之間勋陪，不得越界
舉個例子證明（考點)：
Ω標記：漸進下界
如圖贪磺，和圖一相比，它沒有上界要求诅愚，圖一上下均不能越界寒锚，它只有下界要求，所以叫做漸近下界
O：漸近上界
和Ω標記類似，上邊不越界刹前，下邊不做要求
o標記：非漸進緊確的上界泳赋，圖一Θ是漸進緊確的，而O可以是Θ
也可以不是腮郊，而o有點像集合中真包含的概念摹蘑，它不是Θ的O
w(那個很像w的符號筹燕，不記得咋打出來了)標記符：和o相反轧飞，非漸進緊確的下界
通過上邊幾個圖的理解，下邊表里邊的式子就很好理解了
左邊是滿足的表達式撒踪，右邊是兩者的相對增長速度
這也是比較兩個函數(shù)之間增長速度的方法（n足夠大的時候过咬，求函數(shù)之比的極限，根據(jù)結(jié)果判斷）
分治策略
概念：將原問題分解成子問題制妄，子問題與原問題一樣掸绞，至少規(guī)模更小，直到規(guī)模足夠小耕捞，遞歸停止衔掸，問題得以解決
包括的例子有，歸并排序俺抽、實驗中的gray碼問題
分治算法的分析：
分治法解題的一般步驟
（1）分解敞映，將要解決的問題劃分成若干規(guī)模較小的同類問題；
（2）求解磷斧，當子問題劃分得足夠小時振愿，用較簡單的方法解決；
（3）合并弛饭，按原問題的要求冕末，將子問題的解逐層合并構(gòu)成原問題的解。
三個求解分治法Θ或Ω的方法
1侣颂、代入法
即假設(shè)一個界档桃，然后數(shù)學歸納法證明
這種方法需要經(jīng)驗的積累，可以通過轉(zhuǎn)換為先前見過的類似遞歸式來求解憔晒。
2胳蛮、遞歸樹法
在遞歸樹中，每一個結(jié)點都代表遞歸函數(shù)調(diào)用集合中一個子問題的代價丛晌。將遞歸樹中每一層內(nèi)的代價相加得到一個每層代價的集合仅炊，再將每層的代價相加得到遞歸式所有層次的總代價。
如歸并排序澎蛛，忘了歸并排序的可以參照這里? 歸并排序
這是其遞歸式
這是遞歸樹的式子（主方法常用這個式子）
遞歸樹式子需要解釋的地方有
cn其實就是一個函數(shù)f(n),這個函數(shù)所代表的意思是分解和合并步驟所花費的時間抚垄，哈哈
其（f(n)）復(fù)雜度為Θ（n）,由此再去理解圖七中的式子就好理解了
下面來用遞歸樹的方法求分治算法的漸進界：
下邊這是ppt上的例子，怎么理解這個遞歸樹例子呢，最頂層是cn,從它開始遞歸呆馁，首先你可以把n理解為2的某次冪桐经，比如，n是2的4次冪浙滤，所以整個遞歸樹就有(logn)也就是4層阴挣，每一層的代價剛好都是cn，可求出其T（n）,第5層也就是常量的纺腊，為Θ（n）畔咧，也可以回去圖八和圖七解釋，哈哈
這個例子也一樣揖膜，只不過不是遞歸成一樣的問題誓沸，是兩個一樣的子問題
3、主方法法
它可以瞬間估計一個遞推式的算法復(fù)雜度壹粟。但是我們知道拜隧，這后面肯定是嚴格的數(shù)學證明在支撐著，對于我們用戶來說趁仙，我們只用知道怎么用就行了洪添。
T(n) = aT(n/b) + f (n) ,函數(shù)f(n),這個函數(shù)所代表的意思是分解和合并步驟所花費的時間
下圖就是主定理，記住就行雀费，也可以自己去推導(dǎo)一蛤~
PPT上這樣說主定理干奢，一樣的
下面貼一段gray碼問題的分治解法
第一次寫簡書，寫的亂亂的坐儿，明天將推出動態(tài)規(guī)劃和毛概律胀，希望寫的更好，祝大家期末取得好成績~
