算法設(shè)計(jì)與分析復(fù)習(xí)要點(diǎn)(學(xué)生版)

1、.算法設(shè)計(jì)與分析復(fù)習(xí)要點(diǎn)一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）二、填空題（本大題共15空，每空1分，共15分）三、分析題（本大題共5小題，每小題5分，共25分）四、綜合題（本大題共4小題，1、2題每題6分，3題8分，4題10分，共30分）第2章，導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)：什么是算法, 算法的5個(gè)特性；對(duì)一個(gè)算法作出全面分析的兩個(gè)階段。P24O(g(n)，(g(n)，Q(g(n)的含義。多項(xiàng)式時(shí)間算法：可用多項(xiàng)式（函數(shù)）對(duì)其計(jì)算時(shí)間限界的算法。 常見的多項(xiàng)式限界函數(shù)所表示算法時(shí)間復(fù)雜度的排序： (1) <(logn) < (n) < (nlogn) < (n2

2、) < (n3)Ø 指數(shù)時(shí)間算法：計(jì)算時(shí)間用指數(shù)函數(shù)限界的算法 常見的指數(shù)時(shí)間限界函數(shù)： (2n) < (n！) < (nn)什么是算法的復(fù)雜性：是該算法所需要的計(jì)算機(jī)資源的多少，它包括時(shí)間和空間資源。復(fù)習(xí)棧和隊(duì)列、樹、圖的基本知識(shí)，了解二元樹、完全二元樹，滿二元樹、二分檢索樹、了解圖的鄰接矩陣和鄰接表存儲(chǔ)方法。能寫出圖的深度優(yōu)先序列和廣度優(yōu)先序列。會(huì)求如下一些簡單的函數(shù)的上界表達(dá)式：3n2+10n =O(n2)第3、4章 遞歸與分治算法理解遞歸算法的優(yōu)缺點(diǎn)，深刻理解遞歸算法的執(zhí)行過程。如能寫出解決n階漢諾塔問題的解，并能分析寫出3階漢諾塔問題的遞歸執(zhí)行軌跡。遞歸算

3、法的優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來很大方便。遞歸算法的缺點(diǎn)：運(yùn)行效率較低，耗費(fèi)的計(jì)算時(shí)間和占用的存儲(chǔ)空間都多。為了達(dá)到此目的，根據(jù)具體程序的特點(diǎn)對(duì)遞歸調(diào)用工作棧進(jìn)行簡化，盡量減少棧操作，壓縮棧存儲(chǔ)空間以達(dá)到節(jié)省計(jì)算時(shí)間和存儲(chǔ)空間的目的。能求解或證明常見遞歸關(guān)系式，如n階漢諾塔問題的算法時(shí)間復(fù)雜度。分治法的基本思想：是將一個(gè)規(guī)模為N的問題分解為K個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同。遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。掌握二分檢索算法，如給一個(gè)實(shí)例，可以模擬出low，hig，mid的運(yùn)行軌跡。知道

4、并能證明二分檢索算法平均時(shí)間復(fù)雜度是Q( logn)掌握找最大和最小元素的遞歸分治算法。理解并掌握歸并分類（歸并排序）算法，能畫出用二元樹表示的歸并分類調(diào)用過程及合并過程。理解并能證明歸并分類算法的時(shí)間復(fù)雜度。合并排序的時(shí)間復(fù)雜度是：T(n)=O(nlogn)。利用該遞歸式求取合并排序算法時(shí)間復(fù)雜度的上界。理解并掌握快速分類（快速排序）算法，給定一個(gè)未排序數(shù)組，能分步寫出快速分類中劃分的執(zhí)行過程。理解快速分類算法的時(shí)間復(fù)雜度。快速排序的時(shí)間復(fù)雜度是：T(n)=O(nlogn)本章作業(yè)：1、寫出用分治法求解循環(huán)賽日程表的完整程序。程序語言任意，但必須能上機(jī)運(yùn)行。2、p99-4.22、P99-4.

5、3根據(jù)4.2節(jié)開始所給出的二分檢索策略，寫一個(gè)二分檢索的遞歸過程。3、P99-4.5作一個(gè)“三分”檢索算法，它首先檢查n/3處的元素是否等于某個(gè)x的值，然后檢查2n/3處的元素。這樣，或者找到x，或者把集合縮小到原來的1/3。分析此算法在各種情況下的計(jì)算復(fù)雜度。第5章 貪心方法貪心方法:是根據(jù)具體的問題, 選取一種量度標(biāo)準(zhǔn),按此標(biāo)準(zhǔn)對(duì)n個(gè)輸入進(jìn)行排序, 然后按該順序一次輸入一個(gè)量. 如果這個(gè)輸入量和當(dāng)前的部分最優(yōu)解加在一起不能產(chǎn)生一個(gè)可行解, 則不把此輸入量加入到這個(gè)部分解中, 這種能夠得到某種量度意義下的最優(yōu)解的分級(jí)處理方法就是貪心方法。貪心選擇性質(zhì)：指所求問題的整體最優(yōu)解可以通過一系列局部

6、最優(yōu)的選擇。貪心算法的基本要素：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。掌握背包問題的貪心解法，分別以重量、效益值，單位重量效益值為最優(yōu)量度所得最優(yōu)解的比較。三元?dú)w并模式的貪心解法和證明，能畫出3元?dú)w并樹單源點(diǎn)最短路徑的貪心解法，算法執(zhí)行運(yùn)行蹤跡。如：給出一個(gè)帶權(quán)圖，能將下表的運(yùn)行蹤跡圖補(bǔ)充完整迭代S選取的結(jié)點(diǎn)udist2dist3dist4dist5置初值1-10maxint30100123作業(yè)：P121： 5.2、5.12第6章 動(dòng)態(tài)規(guī)劃將問題分解成多級(jí)或許多子問題，然后順序求解子問題，前一個(gè)子問題的解為后一個(gè)子問題的求解提供有用的信息。最優(yōu)子結(jié)構(gòu)性質(zhì)：該問題的最優(yōu)解包含著其子問題的最優(yōu)解。動(dòng)態(tài)規(guī)劃

7、算法的基本要素：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)。理解并掌握多段圖的動(dòng)態(tài)規(guī)劃求解過程，包括遞推步驟。如，下面是一個(gè)多段圖問題，為了求出源點(diǎn)s到終點(diǎn)t的最短距離，假設(shè)用cost(i)表示節(jié)點(diǎn)i到終點(diǎn)t的距離(節(jié)點(diǎn)i是指下圖中圓圈中的數(shù)字為i的結(jié)點(diǎn))。試根據(jù)cost(i)的含義用動(dòng)態(tài)規(guī)劃的方法求出該多段圖問題的解。（要求根據(jù)cost(i)的含義，用遞推的方法寫出求解步驟，得到結(jié)果）理解并掌握0/1背包問題的動(dòng)態(tài)規(guī)劃求解過程，會(huì)采用序偶直接解n值不大的0/1背包問題。第8章 回溯法回溯法：是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的搜索算法。這在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索

8、至解空間樹的任一結(jié)點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則跳過對(duì)以該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。理解回溯法的基本思想，掌握狀態(tài)空間樹的畫法及各種含義。掌握n皇后問題的算法及執(zhí)行蹤跡。能畫出0/背包問題的狀態(tài)空間樹及子集樹?；厮莘ㄐ实囊蛩兀海?）產(chǎn)生xk的時(shí)間。（2）滿足顯約束的xk值的個(gè)數(shù)。（3）計(jì)算約束函數(shù)constraint的時(shí)間。（4）計(jì)算上界函數(shù)bound的時(shí)間。（5）滿足約束函數(shù)和上界函數(shù)約束的所有xk的個(gè)數(shù)第9章 分支限界法（了解）分支限界法的基本思想：(1)分支限界法常以廣度優(yōu)先或以最小耗費(fèi)(最大效益)優(yōu)先的方式 搜索問題的解空間樹。(2)在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。(3)此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程，這個(gè)過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表這空時(shí)為止。最常見的分支限界法有兩種：隊(duì)列