第6章 變治法

預(yù)排序：用于下列場(chǎng)景,，檢驗(yàn)數(shù)組中元素的唯一性,，查找數(shù)組中出現(xiàn)次數(shù)最多的元素，等等

高斯消去法：將矩陣變成一個(gè)上三角陣,，然后從最后一個(gè)方程開始,，反向替換得到原方程的解。
為了減少舍入誤差,，每次選取第i列系數(shù)絕對(duì)值最大的行,，并且與當(dāng)前行交換。

LU分解：高斯消去法得到的上三角陣為U,，在消去過(guò)程中行的乘數(shù)構(gòu)成了下三角陣L（假設(shè)不存在行交換的情況下）,。比如，在消去第i列的時(shí)候,，把第i行乘以a加到第j行上,，那么U[j][i] = -a。如果存在行交換的話,，那么L也要做相應(yīng)的交換,。可以證明 A=LU
那么方程組Ax=b就等價(jià)于 LUx=b,。
假設(shè)y=Ux,，那么Ly=b，因?yàn)長(zhǎng)是下三角陣,，所以容易求出y,。
Ux=y，所以也容易求出x,。
優(yōu)點(diǎn)：只需做一次LU分解,，然后對(duì)所有的b都可以求解。

計(jì)算矩陣的逆：AX=I
假設(shè)逆矩陣的第j列為Xj, I的第j列為ej,。
那么原方程便等價(jià)于求n的方程組 A * Xj = ej
可通過(guò)LU分解來(lái)求,。

計(jì)算行列式：高斯消去法的每一步，要么改變行列式的符號(hào),，要么將行列式乘上一個(gè)常量,，要么不變,。最終得到一個(gè)上三角陣，三角陣的行列式等于對(duì)角元之積,。所以容易推得原行列式的值,。

AVL樹：是一棵二叉查找樹，其中每個(gè)節(jié)點(diǎn)的平衡因子定義為該節(jié)點(diǎn)左右子樹的高度差,，這個(gè)因子要么為0要么為1或-1,。 （注意：并不只是根節(jié)點(diǎn)滿足這個(gè)特性,，所有節(jié)點(diǎn)要都滿足）

將一個(gè)節(jié)點(diǎn)插入AVL樹,，可能導(dǎo)致失去平衡，某些節(jié)點(diǎn)的平衡因子變成了2或－2,。通過(guò)旋轉(zhuǎn)操作來(lái)回復(fù)平衡,。旋轉(zhuǎn)分為四種R（右旋），L（左旋）,，LR（先對(duì)節(jié)點(diǎn)r的左子樹左旋,，然后將以r為根的樹右旋），RL,。在插入節(jié)點(diǎn)后,，先找到最靠近插入節(jié)點(diǎn)的不平衡節(jié)點(diǎn)，然后旋轉(zhuǎn)以該節(jié)點(diǎn)為根的樹,。




2-3樹：節(jié)點(diǎn)分為兩種,，2節(jié)點(diǎn)－－包含1個(gè)元素和2個(gè)兒子，3節(jié)點(diǎn)－－包含2個(gè)元素和3個(gè)兒子,，兒子可以為空,。所有的葉子都必須在同一層。
總是將新的鍵插入到葉子里,，如果葉子中的鍵變成了3,，那么將中間的鍵移至父節(jié)點(diǎn)，并且該葉子分裂成了兩個(gè)節(jié)點(diǎn),。分裂過(guò)程可能一直向上進(jìn)行,。

堆和堆排序：略

霍納法則：對(duì)多項(xiàng)式 p(x) = an*x^n + a_(n-1)*x^(n-1) + ... + a0進(jìn)行求值。也可用來(lái)進(jìn)行求冪運(yùn)算,。
#Horner(p[0 .. n], x
#  r = p[n] //p[n]為x的n次項(xiàng)的系數(shù)
#  for(i=n-1; i>=0; i--)
#    r = x*r + p[i]
#  return r

計(jì)算圖中的路徑數(shù)量：假設(shè)圖的鄰接矩陣為A,，那么A^k中的元素A^k[i,j]表示了從頂點(diǎn)i到頂點(diǎn)j存在多少條長(zhǎng)度為k的路徑。

第七章 時(shí)空權(quán)衡
計(jì)數(shù)排序：用于數(shù)組元素在一個(gè)有限范圍內(nèi)的情況,。略,。

字符串匹配的Horspool算法：在長(zhǎng)度為n的文本中尋找某個(gè)長(zhǎng)度為m的子串（模式）M。根據(jù)和模式最后一個(gè)字符對(duì)齊的那個(gè)字符來(lái)決定將模式向后移動(dòng)的距離,。假設(shè)文本中的這個(gè)字符為c,，那么移動(dòng)的距離為：
t(c) = m (if c 不再模式的前m-1個(gè)字符中）
t(c) = 模式中前m-1個(gè)字符中最右邊的c到模式尾部的距離 (else)
最差效率為O(mn),，對(duì)隨機(jī)文本而言，效率為O(n)
#shiftTable(p[0 .. m-1])
#  initialize table with m
#  for(j in 0 .. m-2) do table[p[j]] = m-1-j
#  return table

字符串匹配的Boyer-Moore算法：同上面的算法類似,，但是不光考慮最后一個(gè)位置,。假設(shè)模式的最右邊k個(gè)字符已經(jīng)匹配上了，而第k+1個(gè)字符不匹配,。
a）那么根據(jù)不匹配的字符來(lái)確定的移動(dòng)距離為 d1 = max{ t1(c)-k, 1}
其中t1(c)為Horspool算法中的t(c)
b）也可以根據(jù)匹配的k的字符來(lái)確定移動(dòng)距離d2,。假設(shè)模式中最后的k個(gè)字符組成字符串suff(k)，如果模式中還存在這樣一個(gè)字符串,，那么只要移動(dòng)到最右邊的這樣一個(gè)字符串,。如果模式中不存在令一個(gè)suff(k)，就找出模式中最長(zhǎng)的前L個(gè)字符組成的前綴,，使得該前綴等于suff(L),。
總是選擇a和b中最大的距離來(lái)移動(dòng)。
if(k==0) d = d1; else d = max{ d1, d2 }

閉散列（開放尋址法）：用循環(huán)數(shù)組還存放,。沖突的解決：插入時(shí),，若該位置已經(jīng)被占，則向后移,，直到找到一個(gè)空位,；刪除時(shí)，不能簡(jiǎn)單地將該位置清空,，而應(yīng)放置一個(gè)標(biāo)記,。 雙散列法：遇到?jīng)_突時(shí)，并不是向后移動(dòng)一個(gè)位置,，而是每次移動(dòng)s個(gè)位置,，s是根據(jù)另一個(gè)散列函數(shù)S計(jì)算出來(lái)的，假設(shè)鍵為K,，則s＝S(k),，移動(dòng)距離為s, 2s, 3s, ...

B樹：1)根要么為葉子，要么有2到m個(gè)子女 2)內(nèi)部節(jié)點(diǎn)具有ceil(m/2)到m個(gè)子女 （也就是具有ceil(m/2)-1到m－1個(gè)鍵） 3)所有葉子都在最底層,。 m稱為B樹的次數(shù),。 操作類似2-3樹。m=2時(shí)稱為2-3-4樹