《《算法分析與設(shè)計(jì)》》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、《算法分析與設(shè)計(jì)》一、記得哪些算法復(fù)雜性的知識(shí)？用自己的話簡(jiǎn)述。算法復(fù)雜性分為時(shí)間復(fù)雜性和空間復(fù)雜性。在一般的應(yīng)用中，著重考慮時(shí)間復(fù)雜性。除非在一些內(nèi)存比較少的嵌入式應(yīng)用中，才兩方面都考慮。而時(shí)間復(fù)雜性一般只考慮最好、最壞和平均三種情況。最有價(jià)值的一般是考慮最壞情況的時(shí)間復(fù)雜性，因?yàn)樗且粋€(gè)算法運(yùn)行時(shí)間的上界。當(dāng)然，也要考慮平均情況下的時(shí)間復(fù)雜性，比如快速排序，在最壞情況下的時(shí)間復(fù)雜度為0（22）,而在平均情況下是O（nlogn）o事實(shí)證明，快排是個(gè)很好的算法，在很多情況下快拍都能以最快速度完成排序。町以

2、用復(fù)雜性的階描述算法的復(fù)雜性。二、算法的時(shí)間復(fù)雜性分析1、如何根據(jù)算法的結(jié)構(gòu)分析算法的時(shí)間復(fù)雜性？根據(jù)算法的基木操作重復(fù)執(zhí)行的次數(shù)來衡量算法的時(shí)間復(fù)朵性。2、分析遞歸算法的方法，歸方程方法和遞歸樹。解遞歸方程有迭代法（遞推）法解遞歸方程，或套用公式）遞歸樹的方法需利用樹的基本概念求樹高或樹的總結(jié)點(diǎn)數(shù)。1、若對(duì)干某常數(shù)。0,有例7[n)=97{nl3)+na=9?尿3,彳〃)=久冷）如叱）必麗刁（丿3log”）n￡€(0.】]例：歸并排序的遞歸方程：T(n)=2T(n/2)+cn由于3=2,6=2,10^3

3、=1有1和所有充分大的正整數(shù)ri^aftnlb)LTS)=aT(n/by^c

4、nhassolution?ifT00=O(f0;?ifa^h.T(w)a〃log/0：?ifa>b.TS尸o(”W)Master定理式和Master定理遞歸樹的重點(diǎn)就是根據(jù)算法執(zhí)行步驟畫圖，然后加起來再計(jì)算。3、常見算法的時(shí)間復(fù)雜性，例如快速排序、歸并排序、折半查找、最小生成樹，多段圖。算法時(shí)間復(fù)雜度快速排序O(nlogn)歸并排序O(nlogn)拆半查找O(logn)最小生成樹Prim算法：O(nA2);Kruskal算法：O(eloge)多段圖O(n+m),n為節(jié)點(diǎn)，m為邊數(shù)三、學(xué)習(xí)了分治法、動(dòng)態(tài)規(guī)劃

5、、貪心法、回溯法、分支限界的思考策略、基本原理后，你的收獲是什么？是否改變了看問題的角度和思維方式?不同的問題有不同的解法，根據(jù)實(shí)際問題出發(fā)，抓住基木點(diǎn)，分析問題現(xiàn)狀,得到數(shù)學(xué)模型，再根據(jù)數(shù)學(xué)模型求解。四.分治法的基本步驟？學(xué)過哪幾種分割子問題的方法，各有什么特點(diǎn)？分析時(shí)間復(fù)雜性的方法?；静襟E：分解：將原問題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問題形式相同的子問題；解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問題合并：將各個(gè)了問題的解合并為原問題的解。分割方法：①均勻分割：方法簡(jiǎn)單，但

6、是可能會(huì)遇到極端情況導(dǎo)致效率不高。②隨機(jī)分割：隨機(jī)分割可以很好的避免一些極端情況，提高效率。時(shí)間復(fù)雜性分析：一個(gè)分治法將規(guī)模為n的問題分成k個(gè)規(guī)模為n/m的子問題去解。設(shè)分解閥值nO=l,且解規(guī)模為1的問題耗費(fèi)1個(gè)單位時(shí)間。再設(shè)將原問題分解為k個(gè)子問題以及用merge將k個(gè)子問題的解合并為原問題的解需用f(n)個(gè)單位時(shí)間。用T(n)表示該分治法解規(guī)模為n的問題所需的計(jì)算時(shí)間，則有：T(n)=kT(n/m)+f(n)五、設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法包含哪些關(guān)鍵步驟？動(dòng)態(tài)規(guī)劃方程的含義?對(duì)于給出的實(shí)例，如何自底向上求解?

7、關(guān)鍵步驟：(1)分析最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。(2)遞歸的定義最優(yōu)解。(3)以自底向上或自頂向下的記憶化方式(備忘錄法)計(jì)算岀最優(yōu)值(4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造問題的最優(yōu)解動(dòng)態(tài)規(guī)劃方程：動(dòng)態(tài)規(guī)劃方程可以方便了解遞歸過程，進(jìn)行自底向上的求解。實(shí)例：設(shè)P(i,j)是一條從Vi中的結(jié)點(diǎn)j到匯點(diǎn)t的最小成本路徑，COST(i,j)是這條路的成本。則從Vi屮節(jié)點(diǎn)j至肛的最小代價(jià)為：cost((i,j)=min{cost(i+l,l)+c(j,l)},1^Vi+1,jVi2411n6C0ST(3,6)

8、=min{6+COST(4,9),5+COST(4,10))=7C0ST(3,7)=min{4+COST(4,9),3+COST(4,10))=5C0ST(3,8)=7C0ST(2,2)=min{4十C0ST(3,6),2+COST(3,7),1+COST(3,8)}=7C0ST(2,3)=9C0ST(2,4)=18C0ST(2,5)=15COST(1,l)=min{9+COST(2,2),7+COST(2,3),3+COST