算法設(shè)計(jì)與分析復(fù)習(xí)講義

1、課程介紹sina微博 資料下載 通知116周教學(xué) 1718周復(fù)習(xí)答疑 1920考試周考試卷面 60% 考平時(shí)所講知識(shí)點(diǎn) 不考編程 考前有復(fù)習(xí)題庫(kù)平時(shí)成績(jī) 40% 作業(yè)=上機(jī)實(shí)驗(yàn) 自選題目交十次，或大作業(yè)（需同意）上機(jī)：南海樓209 每周四下午 14:0016:00 Java 16:0018:00數(shù)據(jù)結(jié)構(gòu)交作業(yè)，可在宿舍做上課出勤課程定位：計(jì)算機(jī)基礎(chǔ) = 編程語(yǔ)言 = 數(shù)據(jù)結(jié)構(gòu) = 算法 = 復(fù)雜性理論，專題方向橫向擴(kuò)充，縱向深入教材 參考書(shū) 做題 學(xué)習(xí)方法：編程基礎(chǔ)是前提，自學(xué)最重要收集：面試題，算法題，編程題，智力題引論一些數(shù)學(xué)公式估計(jì)調(diào)和級(jí)數(shù)前n項(xiàng) 1/x積分得對(duì)數(shù) 1/x和1/(x+1)

2、所夾估計(jì)誤差 前若干項(xiàng)精確計(jì)算，后面誤差小 P10題1.7P10題1.8P10題1.9 Fibonacci數(shù)的通項(xiàng)：母函數(shù)，z變換計(jì)算機(jī)中的數(shù)進(jìn)制轉(zhuǎn)換：Dec Bin Hex Oct整數(shù)轉(zhuǎn)換：Dec Int = Bin模二 任意進(jìn)制帶權(quán)相加：Bin Int/Float = Dec 任意進(jìn)制浮點(diǎn)數(shù)除法：4/3轉(zhuǎn)二進(jìn)制 任意進(jìn)制二進(jìn)制的乘除法 x*3整數(shù)編碼：補(bǔ)碼浮點(diǎn)數(shù)編碼：IEEE 754，二進(jìn)制科學(xué)計(jì)數(shù)法，能表示的浮點(diǎn)數(shù)個(gè)數(shù)是有限的，能表示的浮點(diǎn)數(shù)的精度是有限的，浮點(diǎn)數(shù)在數(shù)軸上的分布是不均勻的。HEX 16進(jìn)制編碼有效數(shù)字指數(shù)實(shí)際表示名稱說(shuō)明符號(hào)+指數(shù)純小數(shù)00000000000000000線

3、性區(qū)00000000000012-1022*2-52subnormal minFFFFFFFFFFFFF2-1022 *(1-2-52)subnormal max00100000000000001+0-10222-1022realmin3CB00000000000001+0-522-52eps精度，HEX 0.00000000000013FF00000000000001+0013FFFFFFFFFFFFFFF2-eps02-eps屏幕顯示2.0000.40000000000000001+012屏幕顯示240080000000000001+1/2137FEFFFFFFFFFFFFF2-eps10

4、23(2-eps)*21023realmax7FF0000000000000infx/07FFxxxxxxxxxxxxxNaN0/0; 一般FFF 8000000000000考慮 -0，-infMatlab演示 format long format hex format short format1 / 0 = inf0 / 0 = NaN運(yùn)算時(shí)階碼調(diào)整/對(duì)齊 1/2 4+11+eps = HEX 3FF 00000000000012+eps = HEX 400 0000000000000浮點(diǎn)數(shù)的誤差：x=1+eps, x-1 x=2+eps, x-2x=4/3-1, y=3*x, z=1-y程

5、序中的數(shù)據(jù)數(shù)組：下標(biāo)指針：地址；內(nèi)存看作巨大的字節(jié)數(shù)組，下標(biāo)結(jié)構(gòu)；首地址+偏移=實(shí)際地址本質(zhì)上都是地址/指針內(nèi)存，磁盤：巨大數(shù)組 段頁(yè)式/扇區(qū)、簇、文件分配 碎片算法分析時(shí)間復(fù)雜度1 for ( int i = 0; i n; i + )for ( int j = 0; j (int) Math.sin( n ); j + ) foo();P11 P12法則3 P26題2.3 P26題2.4有一個(gè)時(shí)間復(fù)雜度為n2的程序，當(dāng)n=103時(shí)運(yùn)行了1s，當(dāng)n=106時(shí)要運(yùn)行多長(zhǎng)時(shí)間？題數(shù)組順序查找：n數(shù)組二分查找：ln(n)數(shù)組翻轉(zhuǎn)兩/三個(gè)有序數(shù)組合并矩陣存儲(chǔ)矩陣的一維數(shù)組存儲(chǔ)n2、打印三角陣的一維數(shù)

6、組存儲(chǔ)n2/2 打印對(duì)稱陣Toeplitz陣最大定長(zhǎng)子序列和：求積分最大子序列和，不定長(zhǎng)：n3, n2求積分，轉(zhuǎn)為求最大增長(zhǎng)式落差。注意最大子序列，起點(diǎn)一定是終點(diǎn)前的最小值，終點(diǎn)一定是起點(diǎn)后的最大值。從前往后掃描積分序列，求以當(dāng)前點(diǎn)為終點(diǎn)的最大增長(zhǎng)落差：記錄迄今為止最小值，與當(dāng)前值之差就是。再參見(jiàn)P21算法4，里面的ThisSum就是以當(dāng)前點(diǎn)為終點(diǎn)的最大子序列，其清零對(duì)應(yīng)在積分序列里，每次碰到迄今最小值后就清零，所以就是從迄今最小值到當(dāng)前點(diǎn)。直接證明此算法：以ThisSum清零點(diǎn)分段，每段和都=0，反向積分就一定=0。所以，以當(dāng)前點(diǎn)為終點(diǎn)的最大子序列，必以最后一個(gè)ThisSum清零點(diǎn)位起點(diǎn)；起

7、點(diǎn)再往前延伸是不會(huì)使和增大的。P28題2.12最小子序列和：考慮負(fù)數(shù)最小正子序列和：不會(huì)是要求子序列內(nèi)全正數(shù)，求子序列和最小，如此取最小正數(shù)即可。應(yīng)該是要求所有子序列中，和為正，最小。掃描積分序列，對(duì)每個(gè)當(dāng)前元素，求前面最接近又小于當(dāng)前元素?？梢杂小Ｗ畲笞有蛄蟹e：考慮對(duì)數(shù)。掃描積分序列，對(duì)每個(gè)當(dāng)前元素，前面按符號(hào)分兩組，按當(dāng)前元素的符號(hào)求正組的最大（可能不存在），負(fù)組的最大。最大公約數(shù) GCD 歐幾里德輾轉(zhuǎn)相除法 a/b=q.r b/r P23最小公倍數(shù) a/x*b/x*x=a*b/x整數(shù)冪 遞歸：分偶數(shù)/奇數(shù)分解 非遞歸：冪次寫成二進(jìn)制 P24P28題2.15 8次乘法算X62 2 3 5

8、10 15 30 60 62（盡量折半） 窮舉搜索前n個(gè)自然數(shù)取m個(gè)不重復(fù) 數(shù)組亂序P27題2.7：每個(gè)球放入前面的盒子，證明等概率：歸納，n成立，考慮n+1時(shí)的最后一步：最后一個(gè)球放入每個(gè)盒子比例相等；前n個(gè)球的任一個(gè)，已經(jīng)均勻隨機(jī)放入前n個(gè)盒子；前n個(gè)盒子再以1/(n+1)的比例調(diào)入n+1號(hào)盒子，共計(jì)n/(n+1)；以n/(n+1)的比例留在原地。每個(gè)球放入后面的盒子，證明等概率：第一個(gè)球等概率，后面的球是從n個(gè)里面取n-1個(gè)，概率是均勻的，依此類推。一次多項(xiàng)式求值 P28題2.10有序數(shù)組中，尋找元素值=下標(biāo) P28題2.11 折半，ak找前一半判斷素?cái)?shù)P28題2.13篩素?cái)?shù)P28題2.

9、14 估計(jì)：第n個(gè)素?cái)?shù)，前n個(gè)自然數(shù)中素?cái)?shù)量，時(shí)間 其中因子 素因子找多數(shù)： 首先證明，在存在嚴(yán)格多數(shù)的元素（主要元素，過(guò)半數(shù)的元素）的前提下，算法得到此元素。分段，m=0作為每段起點(diǎn)。除最后一段外，前面各段：起點(diǎn)元素在段內(nèi)恰占一半（起點(diǎn)元素看作+1，其它元素看作-1，段到m=0結(jié)束）。所以，前面各段，每段內(nèi)主要元素最多占一半。所以，前面總起來(lái)，主要元素最多占一半。所以，最后一段，主要元素過(guò)半。如果最后一段起點(diǎn)不是主要元素，矛盾。再加上驗(yàn)證，就是完整的算法。P28題2.19復(fù)雜且慢些。列表功能讀寫其它取查增刪改getElementAtgetSubList(last)indexOfElement

10、indexOfSubListindexOfMaxindexOfMinaddAtaddAllAtremoveAtremoveRangesetAtlength/sizecompareTogetFirstgetLastcontainsElementcontainsSubListgetMax / getMingetRandomaddFirstaddLastremoveFirstremoveLastremoveAllremoveAllEqualsclearfillswapisEmptyequals實(shí)現(xiàn)ADT P31基于定長(zhǎng)數(shù)組的列表 對(duì)應(yīng)的時(shí)間復(fù)雜度基于增長(zhǎng)數(shù)組的列表鏈表 單向鏈表 雙向鏈表 循環(huán)鏈表

11、P38 靜態(tài)鏈表 P43列表的變化：棧stack FILO P46兩種實(shí)現(xiàn) 隊(duì)列queue FIFO P58 元素循環(huán)數(shù)組循環(huán)：基于循環(huán)增長(zhǎng)數(shù)組的雙端隊(duì)列 Dequeue P58題一元多項(xiàng)式加減乘除 P39基數(shù)排序 P41稀疏矩陣三元組 轉(zhuǎn)置 乘法每行/列作為一個(gè)列表 轉(zhuǎn)置 乘法十字鏈表：P42 轉(zhuǎn)置 乘法 高效遍歷每行/列學(xué)生、課程 P42多對(duì)多映射/二分網(wǎng)的快速互查實(shí)際設(shè)計(jì)：兩個(gè)類，對(duì)象含列表括號(hào)匹配計(jì)數(shù) 多種括號(hào) P52字符串?dāng)?shù)字表達(dá)式求值P62題3.7 涉及快速卷積P62題3.8整數(shù)次冪大整數(shù) 加減乘除P62題3.9 計(jì)算出24000是多少即可 整數(shù)次冪Josephus問(wèn)題：遞歸 P6

12、3題3.10模擬：不論數(shù)組/鏈表，需定位刪除，時(shí)間復(fù)雜度m*n，min(m,n)*nn個(gè)人編號(hào)0,n-1，從0號(hào)開(kāi)始報(bào)數(shù)0,m-1，報(bào)數(shù)為m-1者離開(kāi)，從下一個(gè)人開(kāi)始重新從0開(kāi)始報(bào)數(shù)。對(duì)f(n,m)，第一個(gè)離開(kāi)者的編號(hào)為(m-1)%n，下一個(gè)人編號(hào)為m%n，從他開(kāi)始重新從0開(kāi)始報(bào)數(shù)?，F(xiàn)在總?cè)藬?shù)n-1，從他開(kāi)始從0編號(hào)的話，最終留下者編號(hào)為f(n-1,m)，對(duì)應(yīng)原問(wèn)題編號(hào)(f(n-1,m)+m%n)%n，化簡(jiǎn)得f(n,m)=(f(n-1,m)+m)%n，時(shí)間復(fù)雜度n反轉(zhuǎn)單鏈表 P63題3.12P63題3.15P64題3.22a記錄迄今為止最小值b 不能小于lnN，否則就可以通過(guò)此方法得到小于ln

13、N的基于比較的排序方法了P63題3.23 數(shù)組模擬內(nèi)存指針樹(shù)概念圖 結(jié)點(diǎn)/節(jié)點(diǎn) 邊 有向 無(wú)向 度樹(shù) 度 根 葉 層/深度 子/子樹(shù)/子孫 親/祖先 兄弟 結(jié)點(diǎn)數(shù)=邊數(shù)+1二叉樹(shù) 左/右子 葉子數(shù)=度2數(shù)+1滿（理想平衡樹(shù)） 完全 平衡樹(shù)/森林二叉樹(shù)實(shí)現(xiàn)結(jié)構(gòu)體+指針P66嵌套列表/廣義表鄰接矩陣遍歷打印目錄文件P67個(gè)數(shù) 總大小 平均大小 深度 最大 最小 P69二叉樹(shù) 三序遍歷表達(dá)式 前綴 中綴 后綴字符串算式構(gòu)造表達(dá)式樹(shù)：拆分 無(wú)運(yùn)算優(yōu)先級(jí)無(wú)括號(hào) 有運(yùn)算優(yōu)先級(jí) 有括號(hào) 參考P71已知其中兩序求原樹(shù) 證明三序遍歷/深度優(yōu)先遍歷：遞歸 通用非遞歸廣度優(yōu)先遍歷/層次遍歷：通用非遞歸樹(shù)的廣度優(yōu)先遍

14、歷 深度優(yōu)先遍歷二叉查找樹(shù)（二叉排序樹(shù)）FindMin FindMax Find P74Insert P75Delete P76 P77刪除結(jié)點(diǎn)無(wú)子結(jié)點(diǎn)，即葉結(jié)點(diǎn)：直接刪除有一子：頂替有二子：改為（遞歸）刪除左子樹(shù)最大值/右子樹(shù)最小值，也可以用來(lái)處理有一子的情況懶惰刪除 P77隨機(jī)生成的二叉查找樹(shù)最壞情況下樹(shù)深度/結(jié)點(diǎn)平均深度O(n)：遞增或遞減序列最好情況下樹(shù)深度/結(jié)點(diǎn)平均深度O(ln n)：平衡樹(shù)隨機(jī)生成的二叉查找樹(shù)，平均情況下樹(shù)深度/結(jié)點(diǎn)平均深度 O(ln n) ： P781、任何插入序列等概率，即前n個(gè)自然數(shù)1,n的全排列；并非所有可能的樹(shù)等概率，可能的樹(shù)和全排列并非一一對(duì)應(yīng)。2、隨機(jī)

15、生成的二叉查找樹(shù)所有節(jié)點(diǎn)深度之和為一隨機(jī)變量=左子樹(shù)深度和+右子樹(shù)深度和+n-1。根節(jié)點(diǎn)深度0。3、插入序列首數(shù)就是樹(shù)根，是隨機(jī)的，均勻分布1,n。對(duì)某個(gè)給定的首數(shù)m，左子樹(shù)所含結(jié)點(diǎn)即前m-1個(gè)自然數(shù)1,m-1。4、下面說(shuō)明，在原問(wèn)題中，若給定首數(shù)m，則左子樹(shù)的所有節(jié)點(diǎn)深度之和就是。原插入序列是前n個(gè)自然數(shù)全排列等概率，考慮其中首數(shù)為m的序列，在這樣的序列中，前m-1個(gè)自然數(shù)的每一個(gè)排列是等概率的，因?yàn)榍皀個(gè)自然數(shù)的全排列可以分三步產(chǎn)生：選擇m-1個(gè)位置放前m-1個(gè)自然數(shù)；排列這m-1個(gè)自然數(shù)；排列剩下的自然數(shù)。只要其它兩步確定了，中間一步總是前m-1個(gè)自然數(shù)的全排列。5、同理可說(shuō)明，在原問(wèn)題

16、中，若給定首數(shù)m，則右子樹(shù)的所有節(jié)點(diǎn)深度之和就是。6、 ，其中均勻隨機(jī)地取，對(duì)應(yīng)取。7、 ，其中，得到，遞推公式簡(jiǎn)記為8、 仿照P184推導(dǎo)AVL樹(shù)：基本平衡的二叉查找樹(shù)越平衡查找越快 O(ln n)嚴(yán)格平衡：極端情況下插入慢，例如末端缺一個(gè)結(jié)點(diǎn)，首端插入；平均情況類似B樹(shù)AVL定義 P80-81AVL插入時(shí)調(diào)整：從插入節(jié)點(diǎn)向上找第一個(gè)不平衡節(jié)點(diǎn)P82-86AVL刪除完整過(guò)程：插入/刪除后更新路徑上每結(jié)點(diǎn)層數(shù)信息從插入/刪除節(jié)點(diǎn)向上找第一個(gè)不平衡節(jié)點(diǎn)若未找到，結(jié)束若左層數(shù)=右層數(shù)+2若左左層數(shù)=右層數(shù)+1則為L(zhǎng)L型若左右層數(shù)=右層數(shù)+1則為L(zhǎng)R型若右層數(shù)=左層數(shù)+2若右右層數(shù)=左層數(shù)+1則為R

17、R型若右左層數(shù)=左層數(shù)+1則為RL型assert斷言查/增/刪時(shí)間復(fù)雜度O(ln n)紅黑樹(shù)紅黑樹(shù)性質(zhì) 注意空指針為黑插入：新結(jié)點(diǎn)N初始為紅，記N父P，爺G，叔UP不存在 / N為根 / 空樹(shù)：直接N變黑 wiki情形1P存在P黑：OK wiki情形2P紅，故G存在、非空、黑，U存在U紅：UP變黑，G變紅；對(duì)G遞歸；四種形狀都一樣。 wiki情形3U黑NPG成之字形：N提升，成為下面情況 wiki情形4NPG成一字形：P提升變黑，G變紅 wiki情形5刪除：要?jiǎng)h除某（非空）結(jié)點(diǎn)X。若X有2個(gè)非空兒子，則復(fù)制左兒子最大值（或右兒子最小值）Y到X，改為刪除Y。所以只需討論下面情況：要?jiǎng)h除某結(jié)點(diǎn)X，

18、X有（至少）1個(gè)兒子為空。記另一個(gè)兒子為N（可能也為空）。此時(shí)，刪除X即去掉X，把N上升到X處，即用N代替X。如果X紅，刪除后OK。如果X黑N紅，刪除后N變黑即OK。所以下面只需討論X黑N黑的情況，此時(shí)刪除后，N子樹(shù)缺了一個(gè)黑，需要調(diào)整。對(duì)刪除后的樹(shù)，記N父P，兄弟S，左侄L，右侄R。由于對(duì)稱性，不妨設(shè)N兄（左兒子）S弟。P不存在 / N為根：OK wiki情況1P存在，由刪除前的圖黑色均衡可知，S存在非空，LR存在（可能為空）S紅：S提升，PS交換顏色，成為下面情況 wiki情況2，注意PLR必黑，圖不準(zhǔn)，LR可能為空S黑R紅：S提升，PS交換顏色，R變黑 wiki情況6R黑L紅：只看S子樹(shù)

19、，L提升，LS交換顏色，成為上面情況 wiki情況5L黑P紅：PS交換顏色 wiki情況4P黑：S變紅，改為調(diào)整P wiki情況3伸展樹(shù)了解P90-93B樹(shù)系列分裂與合并 限定每個(gè)節(jié)點(diǎn)只有一個(gè)值：嚴(yán)格平衡的二叉查找樹(shù)實(shí)際使用內(nèi)存非?？?，所以數(shù)據(jù)只要能放進(jìn)內(nèi)存，AVL已很快紅黑樹(shù)實(shí)際效率高，一般有現(xiàn)成類庫(kù)數(shù)據(jù)大到內(nèi)存裝不下，數(shù)據(jù)庫(kù)B樹(shù)數(shù)據(jù)操作讀多寫少，因?yàn)榇罅康膶懖僮魍客瓿桑▽?shí)時(shí)更新少），此時(shí)可使用快排等散列Hash原理（按某規(guī)則）排序后查找：字典，黃頁(yè) O(ln n)Hash查找：電話號(hào)碼，人名Hash函數(shù)的構(gòu)造散列值均勻分布手機(jī)號(hào)碼后四位、末位、前四位、首位人名首字母、末字母字符串字母

20、和 P112字符串前三個(gè)字母 P112推薦Hash函數(shù)：，其中m常取31, 33, 37 P112插入 查找 刪除 O(1)沖突插入時(shí)沖突的解決方法拉鏈 P113Java中的Object.hashCode() HashMap拉鏈 HashTable HashSet開(kāi)放定址 P117 刪除的問(wèn)題線性探測(cè) P117平方探測(cè) P118補(bǔ)充：互素=數(shù)列模q，不重復(fù)地占滿。若有重復(fù)，假設(shè)，其中，則含q因子，顯然不能含q因子。雙Hash P122大數(shù)據(jù)量re-hash太滿時(shí)做 P123可擴(kuò)散列 P125 均勻分布時(shí)效果好，否則索引項(xiàng)太多 實(shí)際中一般固定使用一個(gè)較長(zhǎng)的hash碼海量網(wǎng)頁(yè)文件的存儲(chǔ)與訪問(wèn)：對(duì)u

21、rl進(jìn)行hash，hash碼較長(zhǎng)；存儲(chǔ)文件含url；分布式存儲(chǔ)節(jié)點(diǎn)；多個(gè)對(duì)外服務(wù)節(jié)點(diǎn)，同步含hash碼=存儲(chǔ)節(jié)點(diǎn)映射；訪問(wèn)用戶增加引起對(duì)外服務(wù)節(jié)點(diǎn)增加；節(jié)點(diǎn)文件數(shù)量增加引起存儲(chǔ)節(jié)點(diǎn)增加，文件存儲(chǔ)位置發(fā)生變化，使用雙映射配置文件逐步轉(zhuǎn)移文件。字符串查找暴力法 JavaHash法 K.M.P.B.M.堆/優(yōu)先隊(duì)列定義：二叉完全樹(shù)，堆序數(shù)組實(shí)現(xiàn)：父子節(jié)點(diǎn)下標(biāo)公式 P134插入：末尾上移 P136刪除：交換后根下移 P138初始化堆：O( n ) P141左式堆：P145左式堆合并：大根與小根右子（遞歸）合并（并調(diào)整根）P159題6.9aP159題6.7b排序選擇排序冒泡排序插入排序P165Shell

22、排序P167 先p排序，再q排序，仍然是p排序 pq平衡排序樹(shù)排序堆排序P170歸并排序P173快速排序P177 小數(shù)組P181 分析P183外部排序：內(nèi)部排序+多路歸并桶排序P189基數(shù)排序排序的穩(wěn)定性P196題7.25不穩(wěn)定：選擇 Shell 堆 快排解決穩(wěn)定性的通用方法：增加比較字段基于比較的排序時(shí)間下界P187P196題7.3413球問(wèn)題補(bǔ)P64題3.16f選擇問(wèn)題/中位數(shù)P185小數(shù)據(jù)量：排序；快速選擇大數(shù)據(jù)量：外排等價(jià)關(guān)系（不相交集）像素圖片的同色聯(lián)通集逐行掃描的像素圖片的同色聯(lián)通集；老鄉(xiāng)關(guān)系等價(jià)關(guān)系判斷；等價(jià)類劃分類樹(shù) 數(shù)組表示 P201小樹(shù)添加到大樹(shù)根 P204路徑壓縮 P205圖定義P215表示P216 結(jié)點(diǎn)指針 嵌套列表 矩陣拓?fù)渑判騊217可拓?fù)渑判?無(wú)圈 = 存在結(jié)點(diǎn)入度0可拓?fù)渑判?= 無(wú)圈：反證無(wú)圈 = 存在結(jié)點(diǎn)入度0：反證，去掉出度0的結(jié)點(diǎn)，構(gòu)造圈無(wú)圈 = 可拓?fù)渑判蛏疃葍?yōu)先遍歷 遞歸廣度優(yōu)先遍歷 列表無(wú)權(quán)圖單源最短路徑 廣度優(yōu)先遍歷P220有權(quán)圖單源最短路徑Dijkstra P225無(wú)圈圖P230關(guān)鍵路徑P230Floyd算法 原理 結(jié)果雙矩陣 最短路徑的存儲(chǔ)物理方