算法分析與設(shè)計(jì)
時(shí)間：2024-01-21 23:30:01 | 來源：信息時(shí)代
時(shí)間：2024-01-21 23:30:01 來源：信息時(shí)代
1.算法：是將轉(zhuǎn)入轉(zhuǎn)換成輸出的計(jì)算步驟所組成的序列或描述輸入輸出關(guān)系的特定計(jì)算過程。
2.算法正確性：對(duì)每一個(gè)輸入實(shí)例算法都能終止，并給出正確輸出。
算法正確性有兩個(gè)要素；1是能夠終止。2是結(jié)果正確。
算法設(shè)計(jì)和分析的步驟可概括:
（1）問題的陳述（2）模型的選擇（3）算法的設(shè)計(jì)（4）算法的程序?qū)崿F(xiàn)（5）算法分析。
算法具有以下五大特性
（1）確定性（2）有窮性（3）可行性（4）輸入（5）輸出。
循環(huán)不變式具有以下三個(gè)性質(zhì)： 初始：在循環(huán)的第一次迭代之前，循環(huán)不變式為真。 維持：如果在循環(huán)的某次迭代之前循環(huán)不變式為真，那么在下一次迭代之前，循環(huán)不變式仍然為真。 終止：當(dāng)循環(huán)終止時(shí)，循環(huán)不變式給出有用性質(zhì)，這個(gè)性質(zhì)可以用于證明算法的正確性
3.算法分析：是指對(duì)一個(gè)算法所需要的計(jì)算機(jī)資源進(jìn)行預(yù)測。
考慮算法的好壞主要有以下幾點(diǎn)：（1）執(zhí)行算法所耗費(fèi)的時(shí)間。（2）執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間，其中主要考慮輔助存儲(chǔ)空間。（3）算法應(yīng)易于理解，易于編碼，易于調(diào)試等。
最重要的計(jì)算資源是時(shí)間和空間資源(存儲(chǔ)器)
輸入規(guī)模是輸入元素的個(gè)數(shù)、用二進(jìn)制表示的輸入的總位數(shù)、和用圖中頂點(diǎn)數(shù)和邊數(shù)表示輸入。4.運(yùn)行時(shí)間：是指在某個(gè)輸入時(shí)，算法執(zhí)行操作的次數(shù)或者步數(shù)。
影響程序運(yùn)行時(shí)間的主要因素 ：（1）程序的輸入（2）由編譯系統(tǒng)所產(chǎn)生的代碼程序的質(zhì)量（3）執(zhí)行程序的計(jì)算機(jī)機(jī)器指令的性能與速度（4）程序所依據(jù)的算法的時(shí)間復(fù)雜度。5.最壞情況：是指算法的運(yùn)行時(shí)間是任一輸入運(yùn)行時(shí)間的上界。
算法最壞情況下的運(yùn)行時(shí)間，即對(duì)于規(guī)模n的任何輸入，算法運(yùn)行最長的時(shí)間。之所以這樣，是由于以下三個(gè)原因：1、算法的最壞情況運(yùn)行時(shí)間是任一輸入運(yùn)行時(shí)間的上界 2、對(duì)于某些算法，最壞情況經(jīng)常出現(xiàn) 3、算法的“平均情況”性能常常與最壞情況大致相同。
6.漸進(jìn)表示：是方便地表示算法的最壞情況下，計(jì)算的復(fù)雜度。
算法的復(fù)雜性測度主要有兩個(gè)方面：(1) 空間復(fù)雜度 (2) 時(shí)間復(fù)雜度 7.遞歸：對(duì)自己的調(diào)用。
8.動(dòng)態(tài)：是所作的決策可能依賴當(dāng)前狀態(tài)，而此前所作的決策無。
9.規(guī)劃：意味著一系列的決策。
動(dòng)態(tài)規(guī)劃算法的研制可由4步組成：(1)刻畫最優(yōu)解的結(jié)構(gòu)(2)遞歸定義最優(yōu)解的值(3)以自底向上(或自頂向下)的方式計(jì)算最優(yōu)解的值(4)根據(jù)計(jì)算的結(jié)果，構(gòu)造問題最優(yōu)解。
10.前綴碼：如果我們只用0／1對(duì)字符進(jìn)行編碼，并限定任一字符的編碼都不是另一個(gè)字符編碼的前綴，則稱這樣的編碼為前綴碼
11.哈夫曼編碼：哈夫曼提出的貪心算法可以構(gòu)造最優(yōu)前綴編碼，這樣產(chǎn)生的編碼稱為哈夫曼編碼。
12.最優(yōu)子結(jié)構(gòu):如果問題的最優(yōu)解包含子問題的最優(yōu)解，則問題展示了最優(yōu)子結(jié)構(gòu)。
13.貪心選擇的性質(zhì):通過局部最優(yōu)選擇(貪心)，可以得到問題的全局最優(yōu)解。
14．在矩陣鏈乘問題中，能對(duì)矩陣進(jìn)行分割的叫非平凡矩陣鏈乘。
15．在矩陣鏈乘問題中，不能對(duì)矩陣進(jìn)行分割的叫平凡矩陣鏈乘。
16．動(dòng)態(tài)規(guī)劃算法的運(yùn)行時(shí)間取決于兩個(gè)因素的乘積:
17．特點(diǎn)：此方法的主要特點(diǎn)是通過采用表格技術(shù)。計(jì)算所有子問題的解。計(jì)算的過程從小問題到大問題，并將計(jì)算結(jié)果存儲(chǔ)在一張表中。
18．優(yōu)點(diǎn)：一旦一個(gè)子問題被解決，就存儲(chǔ)其結(jié)果，此后遇到同樣的子問題，就不再重復(fù)計(jì)算。用多項(xiàng)式算法代替指數(shù)算法。
19．應(yīng)用：動(dòng)態(tài)規(guī)劃典型的應(yīng)用領(lǐng)域是組合優(yōu)化問題。
-
網(wǎng)站
-
營銷
-
設(shè)計(jì)
-
運(yùn)營
-
優(yōu)化
-
效率
-
專注
-
電商
-
方案
-
推廣
微信公眾號(hào)
版權(quán)所有? 億企邦 1997-2025 保留一切法律許可權(quán)利。
在線咨詢