《算法基礎(chǔ)》復(fù)習(xí)提綱2009.5.25

1、算法基礎(chǔ)復(fù)習(xí)提綱 2009.5.251 引言(ch1)1.什么是算法及其特征2.問題實(shí)例和問題規(guī)模2 算法初步(ch2)1.插入排序算法2.算法復(fù)雜性及其度量 (1)時(shí)間復(fù)雜性和空間復(fù)雜性； (2)最壞、最好和平均情形復(fù)雜性；3.插入排序的最壞、最好和平均時(shí)間4.歸并排序算法及其時(shí)間復(fù)雜性 3函數(shù)增長率(ch3)1.漸近記號(hào)O、的定義及其使用2.標(biāo)準(zhǔn)復(fù)雜性函數(shù)及其大小關(guān)系3.和式界的證明方法4 遞歸關(guān)系式(ch4)1.替換法(1)猜測解數(shù)學(xué)歸納法證明；(2)變量變換法；2.迭代法(1)展開法；(2)遞歸樹法；3.主定理5 概率分析(ch5)1.雇傭問題及其隨機(jī)算法(略)2.序列隨機(jī)排列的兩種方

2、法及其復(fù)雜性3.在線雇傭問題及其概率分析(略)6 堆排序(ch6)1堆的概念和存儲(chǔ)結(jié)構(gòu)2.堆的性質(zhì)和種類3.堆的操作：建堆；整堆；4.堆排序算法和時(shí)間復(fù)雜性5.優(yōu)先隊(duì)列及其維護(hù)操作7 快速排序(ch7)1.快速排序算法及其最好、最壞時(shí)間和平均時(shí)間2.隨機(jī)快速排序算法及其期望時(shí)間8 線性時(shí)間排序(ch8)1.基于比較的排序算法下界：(nlogn)2.計(jì)數(shù)排序適應(yīng)的排序?qū)ο?、算法和時(shí)間3.基數(shù)排序適應(yīng)的排序?qū)ο?、算法和時(shí)間4.桶排序適應(yīng)的排序?qū)ο?、算法和時(shí)間9 中位數(shù)和順序統(tǒng)計(jì)(ch9)1.最大和最小值的求解方法2.期望時(shí)間為線性的選擇算法3.最壞時(shí)間為線性的選擇算法及其時(shí)間分析10 紅黑樹(ch

3、13)1.紅黑樹的定義和節(jié)點(diǎn)結(jié)構(gòu)2.黑高概念3.一棵n個(gè)內(nèi)點(diǎn)的紅黑樹的高度至多是2log(n+1)4.左旋算法5.插入算法、時(shí)間、至多使用2次旋轉(zhuǎn)6.刪除算法、時(shí)間、至多使用3次旋轉(zhuǎn)11 數(shù)據(jù)結(jié)構(gòu)的擴(kuò)張(ch14)1.動(dòng)態(tài)順序統(tǒng)計(jì)：擴(kuò)展紅黑樹，支持選擇問題(給定Rank求相應(yīng)的元素)，Rank問題(求元素x在集合中的Rank)(1)節(jié)點(diǎn)結(jié)構(gòu)的擴(kuò)展；(2)選擇問題的算法；(3)Rank問題的算法；(4)維護(hù)樹的成本分析；2.如何擴(kuò)張一個(gè)數(shù)據(jù)結(jié)構(gòu)：擴(kuò)張的步驟；擴(kuò)張紅黑樹的定理(略)；3.區(qū)間樹的擴(kuò)張和查找算法(略)12 遞歸與分治法(sch1)1. 遞歸設(shè)計(jì)技術(shù)2. 遞歸程序的非遞歸化3. 算法設(shè)

4、計(jì)(1) 最近點(diǎn)對(duì)； (2) 生成全排列；(3) 大整數(shù)乘法； (4) Stranssen矩陣乘法；13 動(dòng)態(tài)規(guī)劃(ch15)1.方法的基本思想和基本步驟2.動(dòng)態(tài)規(guī)劃和分治法求解問題的區(qū)別3.最優(yōu)性原理及其問題滿足最優(yōu)性原理的證明方法4.算法設(shè)計(jì) (1)多段圖規(guī)劃； (2)矩陣鏈乘法； (3)最大子段和； (4)最長公共子序列；(5) 0-1問題求解； (6)凸多邊形最優(yōu)三角剖分問題；(7) 圖像壓縮問題；14 貪心算法(ch16)1.方法的基本思想和基本步驟2.貪心算法的正確性保證：滿足貪心選擇性質(zhì)3.貪心算法與動(dòng)態(tài)規(guī)劃的比較4.兩種背包問題的最優(yōu)性分析：最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)5.算法

5、設(shè)計(jì) (1)小數(shù)背包； (2) 活動(dòng)安排； (3)找錢問題； (4) 最優(yōu)裝載問題；(5)單源最短路徑；15 回溯法(sch2)1.方法的基本思想和基本步驟2.回溯法是一種深度遍歷的搜索3.術(shù)語: 三種搜索空間, 活結(jié)點(diǎn), 死結(jié)點(diǎn), 擴(kuò)展結(jié)點(diǎn), 開始結(jié)點(diǎn), 終端結(jié)點(diǎn)4.兩種解空間樹和相應(yīng)的算法框架 5.算法設(shè)計(jì)： (1)n后問題； (2) 0-1背包；(3)排列生成問題； (4) TSP問題；(5)符號(hào)三角形問題; (6) 圖的m著色問題；16 分支限界法(sch3)1方法的基本思想和基本步驟2.與回溯法的區(qū)別3.活結(jié)點(diǎn)的兩種擴(kuò)展方式4.0-1背包問題的搜索: FIFO隊(duì)列和優(yōu)先隊(duì)列5.算法設(shè)計(jì) (1)0-1背包問題； (2)裝載問題(略)； (3)單源最短路徑問題；17 隨機(jī)算法(sch4)1. 隨機(jī)算法的定義2. 線性同余法是產(chǎn)生偽隨機(jī)數(shù)的最常用的方法3. 隨機(jī)算法的分類： 數(shù)值隨機(jī)化算法、拉斯維加斯算法、蒙特卡羅算法、舍伍德算法 （1）利用隨機(jī)投點(diǎn)法求解值、計(jì)算定積分；（2）學(xué)過的舍伍德算法包括：快排的隨機(jī)化版本、選擇問題的隨機(jī)化版本；（3）N-后問題的拉斯維加斯算法，及其與回溯法的結(jié)合； (4) 主元素問題的蒙特卡羅算法；18 數(shù)論算法(ch31)1.gcd(a, b)及其表示