算法設計與分析王紅梅第1章緒論

ID:46915310

大?。?11.50 KB

頁數(shù):38頁

時間:2019-11-29

算法設計與分析王紅梅第1章緒論_第1頁
算法設計與分析王紅梅第1章緒論_第2頁
算法設計與分析王紅梅第1章緒論_第3頁
算法設計與分析王紅梅第1章緒論_第4頁
算法設計與分析王紅梅第1章緒論_第5頁
資源描述:

《算法設計與分析王紅梅第1章緒論》由會員上傳分享,免費在線閱讀,更多相關內容在教育資源-天天文庫

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

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

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

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

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

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

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

8、2.1漸進符號(續(xù))3.Θ符號定義1.3若存在三個正的常數(shù)c1、c2和n0,對于任意n≥n0都有c1×f(n)≥T(n)≥c2×f(n),則稱T(n)=Θ(f(n))n0問題規(guī)模n執(zhí)行次數(shù)n0之前的情況無關緊要T(n)c2×f(n)c1×f(n)1.2.1漸進符號(續(xù))例:T(n)=5n2+8n+1當n≥1時,5n2+8n+1≤5n2+8n+n=5n2+9n≤5n2+9n2≤14n2=

當前文檔最多預覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當前文檔最多預覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學公式或PPT動畫的文件,查看預覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權歸屬用戶,天天文庫負責整理代發(fā)布。如果您對本文檔版權有爭議請及時聯(lián)系客服。
3. 下載前請仔細閱讀文檔內容,確認文檔內容符合您的需求后進行下載,若出現(xiàn)內容與標題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯(lián)系客服處理。
关闭