第1章 算法分析與設計緒論.ppt

算法設計與分析 王紅梅編著 普通高校計算機專業(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重要的問題類型 問題的求解過程 分析問題 設計算法 編寫程序 整理結果程序設計研究的四個層次 算法 方法學 語言 工具 1 1 1為什么要學習算法 理由1 算法 程序的靈魂 理由2 提高分析問題的能力 算法的形式化 思維的邏輯性 條理性 1 1 2算法及其重要特性 算法 Algorithm 對特定問題求解步驟的一種描述 是指令的有限序列 算法的五大特性 輸入 一個算法有零個或多個輸入 輸出 一個算法有一個或多個輸出 有窮性 一個算法必須總是在執(zhí)行有窮步之后結束 且每一步都在有窮時間內完成 確定性 算法中的每一條指令必須有確切的含義 對于相同的輸入只能得到相同的輸出 可行性 算法描述的操作可以通過已經(jīng)實現(xiàn)的基本操作執(zhí)行有限次來實現(xiàn) 歐幾里德算法 m n r 例 歐幾里德算法 輾轉相除法求兩個自然數(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)點 流程直觀缺點 缺少嚴密性 靈活性使用方法 描述簡單算法注意事項 注意抽象層次 歐幾里德算法 程序設計語言優(yōu)點 能由計算機執(zhí)行缺點 抽象性差 對語言要求高使用方法 算法需要驗證注意事項 將算法寫成子函數(shù) includeintCommonFactor intm intn intr m n while r 0 m n n r r m n returnn voidmain cout CommonFactor 63 54 endl 歐幾里德算法 偽代碼 算法語言偽代碼 Pseudocode 介于自然語言和程序設計語言之間的方法 它采用某一程序設計語言的基本語法 操作指令可以結合自然語言來設計 優(yōu)點 表達能力強 抽象性強 容易理解使用方法 7 2 1 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 幾何問題 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í)行時間成正比的語句 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 2 大 符號 定義1 2若存在兩個正的常數(shù)c和n0 對于任意n n0 都有T n c g n 則稱T n g n 1 2 1漸進符號 續(xù) 3 符號 定義1 3若存在三個正的常數(shù)c1 c2和n0 對于任意n n0都有c1 f n T n c2 f n 則稱T n f n 1 2 1漸進符號 續(xù) 例 T n 5n2 8n 1當n 1時 5n2 8n 1 5n2 8n n 5n2 9n 5n2 9n2 14n2 O n2 當n 1時 5n2 8n 1 5n2 n2 當n 1時 14n2 5n2 8n 1 5n2則 5n2 8n 1 n2 定理1 1若T n amnm am 1nm 1 a1n a0 am 0 則有T n O nm 且T n nm 因此 有T n nm 1 2 2最好 最壞和平均情況 例 在一維整型數(shù)組A n 中順序查找與給定值k相等的元素 假設該數(shù)組中有且僅有一個元素值為k intFind intA intn for i 0 i n i if A i k break returni 最好情況 出現(xiàn)概率較大時分析最差情況 實時系統(tǒng)平均情況 已知輸入數(shù)據(jù)是如何分布的 通常假設等概率分布 結論 如果問題規(guī)模相同 時間代價與輸入數(shù)據(jù)有關 則需要分析最好情況 最壞情況 平均情況 1 2 3非遞歸算法的分析 算法 非遞歸算法 遞歸算法 例 求數(shù)組最小值算法intArrayMin inta intn min a 0 for i 1 i n i if a i min min a i returnmin 非遞歸算法分析的一般步驟 1 決定用哪個 或哪些 參數(shù)作為算法問題規(guī)模的度量2 找出算法中的基本語句3 檢查基本語句的執(zhí)行次數(shù)是否只依賴于問題規(guī)模4 建立基本語句執(zhí)行次數(shù)的求和表達式5 用漸進符號表示這個求和表達式關鍵 建立一個代表算法運行時間的求和表達式 然后用漸進符號表示這個求和表達式 1 2 4遞歸算法的分析 1 猜測技術 對遞推關系式估計一個上限 然后 用數(shù)學歸納法 證明它正確 關鍵 根據(jù)遞歸過程建立遞推關系式 然后求解這個遞推關系式 2 擴展遞歸技術 3 通用分治遞推式 大小為n的原問題分成若干個大小為n b的子問題 其中a個子問題需要求解 而cnk是合并各個子問題的解需要的工作量 1 2 5算法的后驗分析 算法的后驗分析 Posteriori 也稱算法的實驗分析 它是一種事后計算的方法 通常需要將算法轉換為對應的程序并上機運行 一般步驟 1 明確實驗目的2 決定度量算法效率的方法 為實驗準備算法的程序實現(xiàn)3 決定輸入樣本 生成實驗數(shù)據(jù)4 對輸入樣本運行算法對應的程序 記錄得到的實驗數(shù)據(jù)5 分析得到的實驗數(shù)據(jù) 表格法記錄實驗數(shù)據(jù) 129 799 113 063 91 274 78 692 67 272 53 010 39 992 24 303 11 966 次數(shù) 散點圖記錄實驗數(shù)據(jù) 1 3實驗項目 求最大公約數(shù) 1 實驗題目求兩個自然數(shù)m和n的最大公約數(shù) 2 實驗目的 復習數(shù)據(jù)結構課程的相關知識 實現(xiàn)課程間的平滑過渡 掌握并應用算法的數(shù)學分析和后驗分析方法 理解這樣一個觀點 不同的算法能夠解決相同的問題 這些算法的解題思路不同 復雜程度不同 解題效率