算法設計與分析復習講義

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

2、所夾估計誤差 前若干項精確計算，后面誤差小 P10題1.7P10題1.8P10題1.9 Fibonacci數(shù)的通項：母函數(shù)，z變換計算機中的數(shù)進制轉換：Dec Bin Hex Oct整數(shù)轉換：Dec Int = Bin模二 任意進制帶權相加：Bin Int/Float = Dec 任意進制浮點數(shù)除法：4/3轉二進制 任意進制二進制的乘除法 x*3整數(shù)編碼：補碼浮點數(shù)編碼：IEEE 754，二進制科學計數(shù)法，能表示的浮點數(shù)個數(shù)是有限的，能表示的浮點數(shù)的精度是有限的，浮點數(shù)在數(shù)軸上的分布是不均勻的。HEX 16進制編碼有效數(shù)字指數(shù)實際表示名稱說明符號+指數(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運算時階碼調整/對齊 1/2 4+11+eps = HEX 3FF 00000000000012+eps = HEX 400 0000000000000浮點數(shù)的誤差：x=1+eps, x-1 x=2+eps, x-2x=4/3-1, y=3*x, z=1-y程

5、序中的數(shù)據(jù)數(shù)組：下標指針：地址；內(nèi)存看作巨大的字節(jié)數(shù)組，下標結構；首地址+偏移=實際地址本質上都是地址/指針內(nèi)存，磁盤：巨大數(shù)組 段頁式/扇區(qū)、簇、文件分配 碎片算法分析時間復雜度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有一個時間復雜度為n2的程序，當n=103時運行了1s，當n=106時要運行多長時間？題數(shù)組順序查找：n數(shù)組二分查找：ln(n)數(shù)組翻轉兩/三個有序數(shù)組合并矩陣存儲矩陣的一維數(shù)組存儲n2、打印三角陣的一維數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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