算法設(shè)計(jì)與分析王紅梅第1章緒論

《算法設(shè)計(jì)與分析王紅梅第1章緒論》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、算法設(shè)計(jì)與分析王紅梅編著普通高校計(jì)算機(jī)專業(yè)特色教材精選本書主要內(nèi)容第1章緒論第2章NP完全理論第3章蠻力法第4章分治法第5章減治法第6章動(dòng)態(tài)規(guī)劃法本書主要內(nèi)容（續(xù)）第7章貪心法第8章回溯法第9章分支限界法第10章概率算法第11章近似算法第12章計(jì)算復(fù)雜性理論第1章緒論算法理論的兩大論題：1.算法設(shè)計(jì)2.算法分析1.1算法的基本概念1.1.1為什么要學(xué)習(xí)算法1.1.2算法及其重要特性1.1.3算法的描述方法1.1.4算法設(shè)計(jì)的一般過程1.1.5重要的問題類型問題的求解過程：分析問題→設(shè)計(jì)算法→編寫程序→整理結(jié)果程

2、序設(shè)計(jì)研究的四個(gè)層次：算法→方法學(xué)→語言→工具1.1.1為什么要學(xué)習(xí)算法理由1：算法——程序的靈魂理由2：提高分析問題的能力算法的形式化→思維的邏輯性、條理性1.1.2算法及其重要特性算法（Algorithm）：對(duì)特定問題求解步驟的一種描述，是指令的有限序列。算法的五大特性：⑴輸入：一個(gè)算法有零個(gè)或多個(gè)輸入。⑵輸出：一個(gè)算法有一個(gè)或多個(gè)輸出。⑶有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。⑷確定性：算法中的每一條指令必須有確切的含義，對(duì)于相同的輸入只能得到相同的輸出。⑸可行性：算法描

3、述的操作可以通過已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來實(shí)現(xiàn)。歐幾里德算法mnr例：歐幾里德算法——輾轉(zhuǎn)相除法求兩個(gè)自然數(shù)m和n的最大公約數(shù)1.1.3算法的描述方法⑴自然語言優(yōu)點(diǎn)：容易理解缺點(diǎn)：冗長、二義性使用方法：粗線條描述算法思想注意事項(xiàng)：避免寫成自然段①輸入m和n；②求m除以n的余數(shù)r；③若r等于0，則n為最大公約數(shù)，算法結(jié)束；否則執(zhí)行第④步；④將n的值放在m中，將r的值放在n中；⑤重新執(zhí)行第②步。歐幾里德算法⑵流程圖優(yōu)點(diǎn)：流程直觀缺點(diǎn)：缺少嚴(yán)密性、靈活性使用方法：描述簡單算法注意事項(xiàng)：注意抽象層次N開始輸入m和n

4、r=m%nr=0m=n；n=r輸出n結(jié)束Y歐幾里德算法⑶程序設(shè)計(jì)語言優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行缺點(diǎn)：抽象性差，對(duì)語言要求高使用方法：算法需要驗(yàn)證注意事項(xiàng)：將算法寫成子函數(shù)#includeintCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}voidmain(){cout<

5、序設(shè)計(jì)語言之間的方法，它采用某一程序設(shè)計(jì)語言的基本語法，操作指令可以結(jié)合自然語言來設(shè)計(jì)。優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解使用方法：7±21.r=m%n;2.循環(huán)直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.輸出n;歐幾里德算法1.1.4算法設(shè)計(jì)的一般過程1．理解問題2．預(yù)測(cè)所有可能的輸入3.在精確解和近似解間做選擇4.確定適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)5．算法設(shè)計(jì)技術(shù)6．描述算法7．跟蹤算法8．分析算法的效率9．根據(jù)算法編寫代碼1.1.5重要的問題類型1.查找問題2.排序問題3.圖問題4.組合問題5.幾何問

6、題1.2算法分析1.2.1漸進(jìn)符號(hào)1.2.2最好、最壞和平均情況1.2.3非遞歸算法的分析1.2.4遞歸算法的分析1.2.5算法的后驗(yàn)分析1.2算法分析算法分析（AlgorithmAnalysis）：對(duì)算法所需要的兩種計(jì)算機(jī)資源——時(shí)間和空間進(jìn)行估算時(shí)間復(fù)雜性（TimeComplexity）空間復(fù)雜性（SpaceComplexity）算法分析的目的：設(shè)計(jì)算法——設(shè)計(jì)出復(fù)雜性盡可能低的算法選擇算法——在多種算法中選擇其中復(fù)雜性最低者時(shí)間復(fù)雜性分析的關(guān)鍵：問題規(guī)模：輸入量的多少；基本語句：執(zhí)行次數(shù)與整個(gè)算法的執(zhí)行時(shí)

7、間成正比的語句for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;問題規(guī)模：n基本語句：x++1.2.1漸進(jìn)符號(hào)1.大O符號(hào)定義1.1若存在兩個(gè)正的常數(shù)c和n0，對(duì)于任意n≥n0，都有T(n)≤c×f(n)，則稱T(n)=O(f(n))n0問題規(guī)模n執(zhí)行次數(shù)n0之前的情況無關(guān)緊要T(n)c×f(n)2.大Ω符號(hào)定義1.2若存在兩個(gè)正的常數(shù)c和n0，對(duì)于任意n≥n0，都有T(n)≥c×g(n)，則稱T(n)=Ω(g(n))n0問題規(guī)模n執(zhí)行次數(shù)n0之前的情況無關(guān)緊要T(n)c×g(n)1.

8、2.1漸進(jìn)符號(hào)（續(xù)）3.Θ符號(hào)定義1.3若存在三個(gè)正的常數(shù)c1、c2和n0，對(duì)于任意n≥n0都有c1×f(n)≥T(n)≥c2×f(n)，則稱T(n)=Θ(f(n))n0問題規(guī)模n執(zhí)行次數(shù)n0之前的情況無關(guān)緊要T(n)c2×f(n)c1×f(n)1.2.1漸進(jìn)符號(hào)（續(xù)）例：T(n)＝5n2＋8n＋1當(dāng)n≥1時(shí)，5n2＋8n＋1≤5n2＋8n＋n＝5n2＋9n≤5n2＋9n2≤14n2＝