Chapter0BigOO()即<=洛必達(dá)法則一邊有分母，一邊無分母的，可以兩邊都先乘分母再比較，或再用洛必達(dá)法則例：logn!=0(lognn)因為(n/2)log(n/2)=log(n/2)n/2<=logn!<=lognn=nlogn任何指數(shù)形式>任何多項式形式任何多項式形式>任何對數(shù)形式Chapter1復(fù)雜度計算Mod運算等于一個除法運算的復(fù)雜度一般，計算復(fù)雜度，先看循環(huán)次數(shù)(注意以比特位n計算時，logN=n)，再看循環(huán)內(nèi)復(fù)雜度最高的那個運算n位長數(shù)作加減運算，為O(n)，作乘除法運算為O(n2)乘2,除2,相當(dāng)于移位，是常數(shù)時間運算計算modmod和加減乘除運算規(guī)則相同，也有交換律、結(jié)合律、分配率、替換率例如，21390mod31=(25)xmod31=(32)xmod31=(1)xmod31=1若ax=1modN，則a和x互為modN下的模倒數(shù)，有模倒數(shù)的充要條件是a和N互質(zhì)例：求20mod79的模倒數(shù)用輾轉(zhuǎn)相除法，每個式子標(biāo)記3個數(shù)(除系數(shù)外都標(biāo)記)gcd（20，79）79=3*20+1^gcd（19,20）20=1*15+1gcd（1，19）15=1*19+0gcd(0，1)1=1-0再逆代回去(逆代的每一步都找對應(yīng)gcd時作標(biāo)記的數(shù)，用余數(shù)代換，用被除數(shù)合并)1=1-(1￡-1*19)代換0然后合并1=20*1-鯉=20*(20-1*^)-1^代換1然后合并孩=20*20-21*1^=20*20-21*(79-3*20)代換19然后合并20=83*20-21*79故模倒數(shù)為83,又因模倒數(shù)必須在1至N之間，則為83-79=4Chapter21.分而治之Divideandconquer:T(n)=aT(n/b)+O(nd)在遞歸中的每一層，將處理問題分為a個子問題(即子問題個數(shù)是上一級的a倍)，而每個子問題處理時的對象(函數(shù)的輸入)被分為b份(即對象大小為上一級的1/b)，而每一步的復(fù)雜度為O(nd)2.Mastertheorem:T(n)=O(nd)d>logbaT(n)=O(ndlogn)d=logbaT(n)=O(nlogba)d<logbaMerge算法處理n個元素merge的復(fù)雜度為O(n)T(n/2)是執(zhí)行了logn層遞歸，T(n/b)是執(zhí)行了logbn層遞歸Chapter3DFS(有向圖無向圖都適用)Explore算法只對起始點可達(dá)的點visit，包括previsit和postvisit標(biāo)記Explore(v)會生成以v為根的子搜索樹DFS算法是對G中所有的點用exploreforallvinV:ifnotvisited(v)thenexplore(G,v)DFS算法復(fù)雜度為O(IEI+IVI)因為DFS中，previsit(v)時，對v為根的子搜索樹為陌生的，而postvisit(v)時則對子樹已完全熟悉，所以若u和v是祖先--孩子關(guān)系，則必有［pre(u)，post(u)］包含［pre(v)，post(v)］，否則u，v完全不相交，不可能出現(xiàn)部分相交的關(guān)系，如pre(u)<pre(v)<post(u)<post(v)DAG有向無環(huán)圖對有向圖用DFS算法，若其生成的搜索樹中有回邊<=>該圖存在環(huán)DAG必有至少一個源(入度為0)，和至少一個匯(出度為0)，必可以線性化凡DAG圖問題，必先線性化DAG圖線性化方法一：用DFS算法后，對postnumber降序排序，postnumber越小越靠后DAG圖線性化方法二：從圖中找一個源，刪除它，不斷重復(fù)該過程直至圖為空3.SCC強連通子圖u和v連通指從u->v有路徑，同時從v->u也有路徑可達(dá)對無向圖，連通子圖個數(shù)就是其DFS算法中的搜索樹的棵樹無向圖作出連通子圖的方法：在DFS算法中加個數(shù)組ccnum［v］賦初值為cc(cc=0)，DFS過程中每調(diào)用一次explore則cc++，最后cc值為連通子圖個數(shù)，有相同ccnum值的v即為一個連通子圖對有向圖中所有互相連通的節(jié)點歸為一個個強連通子圖后(一個子圖視為一個節(jié)點)，有向圖成為一個DAG圖，該DAG圖中的源稱為源強連通子圖，其匯稱為匯強連通子圖Lemmal：對一個匯SCC內(nèi)任意一節(jié)點用explore算法，可以剛好visit該子圖內(nèi)所有點(因為互相連通，且因為是匯，故不會visit該SCC以外的點)Lemma2:有向圖的postnumber最大值必存在于其源強連通子圖中Lemma3：若有一條邊是從強連通子圖C通向另一個強連通子圖C’，則C中Maxpostnumber>C’中Maxpostnumber，所以有向圖可以通過對其每個強連通子圖的Maxpostnumber降序排序來線性化有向圖作出其強連通子圖的方法(線性時間)：在其反向圖G’上用DFS算法(G’上的源SCC就是G上的匯SCC，為了應(yīng)用Lemmal，因為只有匯SCC才能一次explore找出該SCC所有點)用無向圖作連通子圖的算法處理G，且DFS過程中對每個節(jié)點以其在(1)中的postnumber降序順序來處理(應(yīng)用Lemma2和Lemma3)Chapter4BFS深度優(yōu)先搜索(有向圖無向圖都適用)bfs(G,s)從s點出發(fā)foralluinVdodist(u)=8；初始距離都賦為無窮dist[s]=0;訪問s,距離設(shè)為0Q=[s]設(shè)一個隊列Q,初始只有s點whileQisnotemptydo隊列為空是終止條件u=Eject(Q);把u移出隊列(loop第一次的時候u即為s)foralledge(u,v)inEdo對所有u能到達(dá)的點ifdist(v)=8then若未訪問過則Inject(Q,v);加入隊列dist[v]=dist[u]+1;距離為u+1每次循環(huán)會先把該層搜索到的點都加入Q,下一層循環(huán)時再eject,并從該點出發(fā)再訪問其可到達(dá)的點，下一層的點距離會多1BFS復(fù)雜度為O(|E|+|V|)注：BFS只考慮distancefroms,所以不會再去搜索s不可達(dá)的點，這和DFS是不同的。BFS視所有邊長度相同(為1),故只能找到邊長都為1的圖中的最短路徑最短路徑算法(有向圖無向圖都適用)當(dāng)邊長度不為1時，利用插入dummy點的思想(如邊長為10,相當(dāng)于該邊上插入9個dummy點后，化為邊長為1),可以用BFS算法計算最短路徑，但如果邊長很長，則算法效率太低。于是再加上setalarm的方法和引入特殊數(shù)據(jù)結(jié)構(gòu)priorityqueue,有了Dijkstra算法Dijkstra算法：從s點出發(fā)作BFS算法，每探索1層，把該層可達(dá)的點的距離值更新，然后選距離數(shù)組中值最小的點，從該點出發(fā)再探索下一層，并更新距離數(shù)組注：loop中每次被選中的距離值最小的點會被移出隊列，故表示它的值已確定下來，之后不會再被更新，隊列為空則算法終止Dijkstra復(fù)雜度：當(dāng)用二叉堆形式的數(shù)組時，為O((|V|+|E|)log|V|)二叉堆：是完全二叉樹(第k層未滿時，不會有第k+1層，左分支未填時不會有右分支)，該數(shù)組中，節(jié)點j的parent為j/2取下界，j的children為2j和2j+1有負(fù)邊的圖最短路徑算法Dijkstra不適用Bellman-Ford算法：repeatV-1times：循環(huán)V-1次foralleinE檢查所有邊，更新其端點的dist值update(e)Bellman-Ford復(fù)雜度為O(|V|?|E|)Bellman-Ford可用于檢定圖中是否有負(fù)環(huán)，只要在V-1次迭代后再多迭代一次，如果仍有dist數(shù)組的更新，則圖中必有負(fù)環(huán)DAG圖最短路徑算法(正邊負(fù)邊都適用)先線性化DAG圖，然后foreachuinV,inlinearizedorderforalledges(u,v)inE對所有u相連的e作update(e)update(u,v)特別地，把DAG圖中所有邊*(-1)后，可以用該算法求最長路徑Chapter5MST最小生成樹有最小的總權(quán)數(shù)的樹是MST(不唯一)Lemmal：移除環(huán)中的一條邊，不會使圖disconnectLemma2：n節(jié)點的樹有n-1條邊Lemma3：任何連接的無向圖G(V,E)，若有E=V-1，則G必為樹Lemma4:無向圖為樹＜=＞任意兩個節(jié)點之間有唯一路徑Kruskal’sMST算法：從空圖開始，每次選一條不會使圖產(chǎn)生環(huán)的權(quán)重最小的邊(貪婪算法一一每次作最符合當(dāng)前利益的選擇)每一次如何高效地挑選不會使圖產(chǎn)生環(huán)的權(quán)重最小的邊？割定理：設(shè)邊集X為G的某個最小生成樹T的子集，任意將G切割成集合S和V-S，使X里沒有邊橫跨S和V-S，則將e加到X中形成的新集合X’也是某個MST的子集，這里e是橫跨S與V-S的所有邊里權(quán)重最小的邊。(即選S時，把X中所有邊都包含進(jìn)去即可)Kruskal’sMST算法實現(xiàn)：foralluinVdomakeset(u);初始用makeset建立V個分離集(每個頂點為一個集合)X={};SorttheedgesEbyweight;foralle={u,v}inEinincreasingorderofweightdoiffind(u)!=find(v)thenadde={u,v}toX;union(u,v)這里find是用來找tree的根，find(u)!=find(v)表示u所在集合的樹根與v所在集合的樹根不同，也就是說u和v不在一個集合內(nèi)union是用來合并兩個集合，union(u,v)合并u所在集合和v所在集合，并選擇樹高較大的集合的根節(jié)點作為合并后的根節(jié)點(只有相同樹高的兩顆樹合并，總樹高才會加1，其它情況合并，樹高都不變)Kruskal算法生成的樹有如下性質(zhì)：Lemma1：非根節(jié)點的rank＜根節(jié)點的rank(rank為在樹中的高度，從葉子往上算)Lemma2：rank為k的樹有至少2k個節(jié)點(k從0開始)Lemma3：若整個樹有n個節(jié)點，則rank為k的節(jié)點至多有n/2k個，即樹最大高度為logn所以Kruskal算法復(fù)雜度為max{O(|E|),O(|V|log|V|)}Chapter6動態(tài)規(guī)劃為解決問題，先定義一組子問題，而原問題的最優(yōu)解由子問題的最優(yōu)解構(gòu)成，逐步追溯子問題至更小的子問題，直至到最簡的形式(某個已知的或顯而易見的解)動態(tài)規(guī)劃與分而治之的差別：都是分解問題，但分治每次將問題分解得更小(通常至少是每次分解為一半)，而動態(tài)規(guī)劃只是分解為稍稍小一點的問題(通常只是f(n)分解至f(n-1))。所以動態(tài)規(guī)劃每次是基于已得到的子問題的最優(yōu)解而進(jìn)行的，不會像分治那樣每次再去計算一遍子問題，那樣的話會變成指數(shù)級運算時間。(也就是說，如果子問題出現(xiàn)大量重疊，則用動態(tài)規(guī)劃將非常有效)復(fù)雜度：Theinputisx1，x2，，xnandasubproblemisx1，x2，...x.則0為O(n)Theinputisx1，x2，，xnandy1，y2，...ymandsubproblemisx1，x2，...x.andy1，y2，...y.則為O(mn).Theinputisx1，x2，...，xnandasubproblemisx.，xi+1，...x.則為O(n2)背包問題n1有重量為w1，w2，...wn的物品，價值分別為v1，v2，...匕裝入容量為W的背包，每個物品可重復(fù)選，求背包所裝的最大價值1K(0)=0;一定要有初始條件(動態(tài)規(guī)劃分解到最簡的子問題)forw=1toWdo填一維表記錄每個子問題的最優(yōu)解，這里子問題是背包容量為1，2,...WK(w)=max{K(w-w.)+v.};因為w-w.<w，所以K(w-w.)必已存在于最優(yōu)解的表中(1<=i<=n，且w.<=w)對所有重量小于當(dāng)前w的物品，求選該物品入包后的總價maxreturnK(W);一定要有return返回原問題的解復(fù)雜度為O(nW)每個物品不可重復(fù)選(物品唯一)，求背包所裝的最大價值K(0)=0;初始條件forj=1tondo填二維表，K(w,.)表示第j個物品加入考慮后容量為w的背包的總價值forw=1toWdoifw.>wthenK(w,j)=K(w,j-1);如果該物品大于當(dāng)前背包容量，則不選，K不變elseK(w,j)=max{K(w-w.,j-1)+v.,K(w,j-1)};這里w-w.指騰出w.的重量來裝第j個物品，價值變?yōu)镵+v.，然后與不選該物品的情況比較，取價值大的JJreturnK(W,n);返回原問題的解復(fù)雜度仍為O(nW)注：一般是否選擇填一維表來把問題分解為子問題，要看是否能從f(i-1)中直接歸納出f(i)，否則要考慮填二維表甚至多維表來分解問題類似背包問題的，一般地，可重復(fù)選，用一維表即可，不可重復(fù)選的，需用二維表，因為在算法過程中，不知道第i種物品是否已被選過，故要加一維來區(qū)分其它典型動態(tài)規(guī)劃問題，包括DAG圖最短路徑問題(一維表)，序列的最長遞增子序列問題(一維表)，兩個字符串的編輯距離問題(二維表)兩個序列的最長公共子序列問題(二維表)，最簡矩陣乘法問題(二維表)Chapter7線性規(guī)劃線性規(guī)劃問題通常會涉及一組變量，需要找出這組變量的某種賦值使其滿足一組由這些變量構(gòu)成的線性方程或不等式，并極大化或極小化某個給定的線性目標(biāo)函數(shù)一般這些方程或不等式構(gòu)成的條件在n維空間(幾個變量就是幾維)中形成一個集合區(qū)間，解線性規(guī)劃問題最優(yōu)解就是找出給定的線性目標(biāo)函數(shù)在該區(qū)間上的最大值或最小值Generalrule:線性規(guī)劃最優(yōu)解存在于可行空間的某個頂點上，除非其無解或無界對偶所有線性最大化問題存在一個對應(yīng)的最小化問題，稱為對偶問題對偶定理：如果一個線性程序存在一個有限的最優(yōu)值，則其對偶問題也存在最優(yōu)值，且兩個最優(yōu)值必相等。例如最大流問題，可以通過對其對偶問題中的變量進(jìn)行適當(dāng)