演算法效率

第一章演算法：效率、分析與量級1.1演算法1.2發展有效率演算法的重要性1.2.1循序搜尋法與二元搜尋法1.2.2費布那西數列(FibonacciSequence)1.3演算法的分析1.3.1複雜度分析1.3.2演算法分析原理的應用1.3.3正確性分析1.4量級(Order)1.4.1以直覺的方式介紹量級的概念1.4.2以嚴謹的方式介紹量級的概念1.4.3使用極限計算量級第一章演算法：效率、分析與量級當我們使用某種技巧解決一個問題的時候，會產生一種逐步執行的程式來解決問題。該種逐步執行的程式及稱為解決這個問題的演算法。1.1演算法串列代表的是一個由某些項目以特定的順序構成的即集合。EX：S=[10,7,11,5,13,8]演算法1.1循序搜尋法(SequentialSearch)演算法1.2加總陣列中的項目演算法1.3交換排序法(ExchangeSort)演算法1.4矩陣乘法1.2發展有效率演算法的重要性1.2.1循序搜尋法與二元搜尋法演算法1.5二元搜尋法(BinarySearch)1.2.2費布那西數列演算法1.6費布那西數列的第N項(遞迴版)定理1.1若T(n)代表演算法1.6相對應的遞迴樹含有的項目數。則對於證明：我們利用在n上執行歸納法來證明歸納基底：我們需要兩個基礎的例子，因為歸納步驟中需要用到前兩個系子的結果。對於n=2及n=3，圖1.2中的遞迴樹顯示歸納假設：產生歸納假設的其中一個方式是，假設對於所有的mn，這個敘述都成立。接著，在歸納步驟中，證明就n而言，此表示同樣的敘述也必須是成立的。我們在這個證明中將使用這個方式。假設對於所有的m，且歸納步驟：我們必須證明。T(n)的值等於T(n-1)與T(n-2)的總和加上一個根節點，因此(根據歸納假設)演算法1.7費布那西數列的第n項(iterative版)演算法1.6&1.7的比較1.3演算法的分析1.3.1複雜度分析基本運算在求得輸入大小後，我們挑選某些指令或指令群阻使得演算法作的工作總和約略與這些指令或指令群組被執行的次數成正比。我們稱這些指令或指令循組為該演算法中的基本運算。時間複雜度分析對一個演算法進行時間複雜度分析就是求得每個不同的輸入大小，該演算法所執行的基本運算次數。分析演算法1.2所有情況的時間複雜度(加總陣列中的項目)除控制指令外，在迴圈中唯一的指令就是把陣列中的一個項目加總到sum這個變數中。因此，我們稱這個指令為此演算法的基本運算。基本運算：將陣列中的一個項目加總到sum這個變數中。輸入大小：n、陣列中的項目個數。無論陣列中所含的數值是什麼，for迴圈會執行n次。因此，基本運算總是被執行n次,故可得T(n)=n分析演算法1.3所有情況的時間複雜度(交換排序法)如同先前所提及，對於利用key的比較來進行排序的演算法，我們可以把比較指令或是指定值指令當作是基本運算來看。我們將在這裡分析比較的次數。基本運算：比較S[j]與S[i]輸入大小：n，被排序的項目個數我們必須求得for-j迴圈執行的次數。給定n，for-i迴圈執行的次數恆為n-1。在for-i迴圈第一次執行過後，for-j迴圈執行n-1次；在for-i迴圈第二次執行過後，for-j迴圈執行n-2次：在for-i迴圈第三次執行過後，for-j迴圈執行n-3次，……，在for-i迴圈最後一次執行過後，for-j迴圈執行1次。因此，for-j迴圈總共執行的次數可由下式求得分析演算法1.4所有情況的時間複雜度(矩陣乘法)在最內層的for迴圈中只有一個由一個乘法與一個加法組成的指令。這個演算法可以被實作成執行的加法個數遠少於執行的乘法個數。因此，我們將只設定乘法指令為基本運算。基本運算：在最內層的for迴圈中的乘法指令輸入大小：n，行數與列數for-i迴圈的執行次數恆為n。for-i迴圈每執行一次，for-j迴圈就執行n次；for-j迴圈每執行一次，for-k迴圈就執行n次。因為基本運算在for-k迴圈的內部，因此最差情況時間複雜度對於一個給定的演算法，W(n)被定義為在輸入大小為n的情況下，該演算法執行基本運算次數的最大值。因此W(n)被稱為該演算法的最差情況時間複雜度，而其求得過程稱為最差情況時間複雜度分析。分析演算法1.1最差情況的時間複雜度(循序搜尋法)基本運算：將x與陣中的一個項目進行比較輸入大小：n，陣列中的項目個數基本運算最多執行n次，也就是當x位於陣列的尾端或x不在陣列中時。因此W(n)=n平均情況時間複雜度分析對於一個給定的演算法，A(n)被定義為在輸入大小為n的情況下，該演算法執行基本運算次數的平均值。因此A(n)被稱為該演算法的平均情況時間複雜度，而其求得過程即稱為平均情況時間複雜度分析。分析演算法1.1平均情況的時間複雜度(循序搜尋法)基本運算：將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)被稱作該演算法的最佳情況時間複雜度，其求得的過程稱為最佳情況時間複雜度分析。分析演算法1.1最佳情況的時間複雜度(循序搜尋法)基本運算：把x與陣列中的一個項目進行比較輸入大小：n，陣列中的項目個數因為，因此迴圈至少會走一次，如果x=S[1]，那麼無論n的大小為何，迴圈都是只走一次。因此B(n)=1記憶體複雜度分析(memorycomplexity)求得一演算法以使用記憶體為單位來計算，其效率為何複雜度函數(complexityfunction)是任一個將正整數映射到非負實數的函數1.3.2演算法分析原理的應用1.3.3正確性分析1.4量級(order)線性時間演算法(linear-timealgorithm)平方時間演算法(quadratic-timealgorithm)1.4.1以直覺的方式介紹量級的概念純平方函數(purequadraticfunction)EX：完全平方函數(completequadraticfunction)EX：常見的複雜度類別表1.3二次項最終會主控整個函數的值1.4.2以嚴謹的方式介紹量級的概念bigO量級的性質1.4.3使用極限計算量級