第一章 演算法：效率、分析与量级.PPT

第一章 演算法：效率、分析與量級 第一章 演算法：效率、分析與量級 1.1 演算法 演算法1.1 循序搜尋法(Sequential Search) 演算法1.2 加總陣列中的項目 演算法1.3 交換排序法(Exchange Sort) 演算法1.4 矩陣乘法 1.2 發展有效率演算法 的重要性 1.2.1循序搜尋法與 二元搜尋法 演算法1.5 二元搜尋法(Binary Search) 1.2.2費布那西數列 演算法1.6 費布那西數列的第N項(遞迴版) 定理1.1 演算法1.7 費布那西數列的第n項(iterative版) 演算法1.61.7的比較 1.3演算法的分析 1.3.1複雜度分析 基本運算 時間複雜度分析 分析演算法1.2所有情況的時間複雜度(加總陣列中的項目) 分析演算法1.3 所有情況的時間複雜度(交換排序法) 分析演算法1.4 所有情況的時間複雜度(矩陣乘法) 最差情況時間複雜度 分析演算法1.1  最差情況的時間複雜度(循序搜尋法) 平均情況時間複雜度分析 分析演算法1.1  平均情況的時間複雜度(循序搜尋法) 最佳情況時間複雜度 分析演算法1.1 最佳情況的時間複雜度(循序搜尋法) 記憶體複雜度分析 (memory complexity) 複雜度函數(complexity function) 1.3.2演算法分析原理的應用 1.3.3正確性分析 1.4量級(order) 1.4.1以直覺的方式介紹量級的概念 常見的複雜度類別 表1.3 二次項最終會主控整個函數的值 1.4.2 以嚴謹的方式 介紹量級的概念 big O 量級的性質 1.4.3使用極限計算量級 基本運算：將x與陣列中的一個項目進行比較 輸入大小：n，陣列中的項目個數 我們首先分析已知x在S中的情況，所有在S中的項目都是相異的，因此沒有理由認為x出現在某個位置的機率大於出現在另一個位置的機率。根據這個資訊，對於 ，x位於第k個位置的機率為1/n。若x位於第k個位置，找到x所需執行的基本運算次數為k。這代表的是平均時間複雜度可以由下式得到 接下來我們分析x可能不在陣列中的情況。若要分析這個情況，我們必須指定x位於從1到n的每個位置之機率都是相同的。X位於第k個位置的機率為p/n，x不在陣列中的機率為1-p。若x在第k個位置被找到，迴圈就跑了k次，若x沒有在陣列中被找到，則迴圈則跑了n次，因此 對於一個給定的演算法，B(n)被定義為在輸入大小為n的情況下，該演算法執行基本運算次數的最小值。因此B(n)被定義為在輸入大小為n的情況下，該演算法執行基本運算次數的最小值。又B(n)被稱作該演算法的最佳情況時間複雜度，其求得的過程稱為最佳情況時間複雜度分析。 基本運算：把x與陣列中的一個項目進行比較 輸入大小：n，陣列中的項目個數 因為 ，因此迴圈至少會走一次，如果x=S[1]，那麼無論n的大小為何，迴圈都是只走一次。因此 B(n)=1 求得一演算法以使用記憶體為單位來計算，其效率為何 是任一個將正整數映射到非負實數的函數 線性時間演算法 (linear-time algorithm) 平方時間演算法 (quadratic-time algorithm) 純平方函數(pure quadratic function) EX： 完全平方函數(complete quadratic function) EX： * * 1.1演算法 1.2發展有效率演算法的重要性 1.2.1循序搜尋法與二元搜尋法 1.2.2費布那西數列(Fibonacci Sequence) 1.3演算法的分析 1.3.1複雜度分析 1.3.2演算法分析原理的應用 1.3.3正確性分析 1.4量級(Order) 1.4.1以直覺的方式介紹量級的概念 1.4.2以嚴謹的方式介紹量級的概念 1.4.3使用極限計算量級 當我們使用某種技巧解決一個問題的