第1章 算法分析與設(shè)計(jì)緒論.ppt

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