演算法复杂度分析范例课件.ppt

《演算法复杂度分析范例课件.ppt》由会员分享，可在线阅读，更多相关《演算法复杂度分析范例课件.ppt（101页珍藏版）》请在三一办公上搜索。

1、1 認識演算法,從食譜到高階程式語言,1.1 演算法名稱的由來,2,阿布迦法穆罕默德賓穆薩阿爾-可瓦里茲米,演算法(Algorithm)一詞源自一位的阿拉伯數學家:阿布賈法穆罕默德賓穆薩阿爾可瓦里茲米(Abu Jafar Muhammad ibn Musa al-Khwarizmi)(780 850 A.D.)的拉丁文譯名(al-Khwarizmi)。,3,阿爾-可瓦里茲米(al-Khwarizmi),阿爾可瓦里茲米將印度所發明的十進位數字記號傳入阿拉伯地區，而阿拉伯商人在經商時則將十進位數字記號傳入歐洲成為現今我們使用的數字記號。更重要的是，阿爾可瓦里茲米著有一本討論有系統地解決一次方程式(

2、linear equation)及一元二次方程式(quadratic equation)的書籍，此書被翻譯成名為”Liber algebrae et almucabala”的拉丁文書籍，啟發了代數學的萌芽，對人類的現代科技與文明發展有相當深遠的影響。代數學的英文名稱 Algebra 就是源自於此書之書名。,4,阿爾-可瓦里茲米(續)(al-Khwarizmi),阿爾可瓦里茲米以一步一步(step by step)的方式，描述算術(arithmetic)運算與一元二次方程式及某些一次方程式的解答過程。稍後我們會知道，這些一步一步描述的解答過程就是我們現今所定義的演算法。這就是為什麼演算法(alg

3、orithm)的名稱是源自於阿爾可瓦里茲米(al-Khwarizmi)的原因。以下我們展示 一元二次方程的解法描述：,5,一元二次方程解法描述,關於解開 x 的方程 ax2+bx=c 的解法,6,1.2 什麼是演算法?,7,什麼是演算法?,廣義的說，演算法是解決某一問題的一步一步程序(a step-by-step procedure for solving a problem)-Merriam-Webster Dictionary狹義的說，演算法是一個由一些步驟所構成的集合，依循這些步驟得以解決數學問題或完成計算機進程(a set of steps that are followed in o

4、rder to solve a mathematical problem or to complete a computer process)-Merriam-Webster Dictionary,8,食譜(recipe)是演算法,9,出處:嘉義市政府衛生局網頁(http:/www.cichb.gov.tw/other/bus_detail.asp?bus_dtl_id=1066),流程圖(flowchart)是演算法,10,其他廣義演算法的例子,企業組織的標準作業程序(Standard Operating Procedure,SOP)也是演算法工作人員面對特定問題時，只要按照步驟指示一步一步

5、進行就能解決問題設備的使用手冊(manual)或故障排除手冊也包含許多演算法因為它包含許多可以用於解決某一問題(例如，如何安裝新設備及解決印表機的卡紙問題等)的一步一步程序。,11,演算法計算角度的嚴謹定義,演算法(algorithm)：由有限(finite)步驟(step)所構成的集合，依照給定輸入(input)依序執行每個明確(definite)且有效(effective)的步驟，以便能夠解決特定的問題；而步驟的執行必定會終止(terminate)，並產生輸出(output)。,12,演算法的特性,根據演算法計算角度的嚴謹定義，演算法是由解決某一特定問題的步驟所組成，具有以下特性:指定輸入

6、(input)：演算法必須指定輸入，可以由外界輸入0 個、1 個或多個資料。具有輸出(output)：演算法必定有至少1 個以上的輸出。有限性(finiteness)：演算法步驟的個數必須是有限的，而且步驟的執行最後會終止(terminate)。明確性(definiteness)：演算法的每個步驟都必須是明確(definite)而不含糊的(unambiguous)。有效性(effectiveness)：演算法的每個步驟必須是有效的(effective)或說是可行的(feasible)。,13,演算法的特性(續),演算法必須指定輸入我們有時會透過介面(例如鍵盤)由外界獲得問題輸入，有時也會將輸入

7、直接寫在演算法中。因此演算法可以由外界輸入0 個、1 個或多個資料。演算法必須要有一個以上的輸出如此演算法才能為人們所用。演算法必須滿足有限性(finiteness)它的步驟個數必須是有限的，而且步驟的執行最後會終止(terminate)；如此，演算法才有可能在執行有限步驟之後終止並產生輸出為人們所用。,14,演算法的特性(續),演算法必須滿足明確性(definiteness)，也就是說它的每一個步驟必須是明確(definite)而不含糊的(unambiguous)。例如，若有一個步驟是加6 或7 到變數x，則這個步驟是不明確的，因為我們可能加6 也可能加7 到變數x 中但是，加亂數生成器(r

8、andom number generator)函數的值到變數x則是明確的步驟，因為我們可以很明確地將亂數產生器函數的值加到變數x又例如，計算5/0是不明確的，因為分母(除數)為0 是沒有明確定義的計算。,15,演算法的特性(續),演算法必須滿足有效性(effectiveness)，也就是說演算法的每個步驟必須是有效的(effective)或說是可行的(feasible)每個步驟即使由人們拿著紙筆，都可以在有限時間內計算出結果。例如，步驟計算出2 完全無誤差的值不滿足有效性，因為它是不可行的，我們需要進行無窮位數的計算才可以得到 2 完全無誤差的值。相反的，計算2 到小數點以下10 位，並捨棄其

9、後位數則滿足有效性，因為它是可行的，人們即使只是藉由紙筆，都可以計算出2=1.4142135623 的結果。,16,1.3 演算法的例子,17,解決正整數m是不是正整數n的倍數問題的流程圖,18,解決正整數m是不是正整數n的倍數問題的C+程式,19,一個既不會終止，也不產生輸出的C程式 不是演算法,20,1.4 如何表示演算法?,21,演算法的表示,一般我們使用以下方式來表示演算法:自然語言(中文或英文等語言)流程圖(flow chart)虛擬碼(pseudo code)以下我們舉一個古老的演算法 歐幾里德演算法(Euclid Algorithm)為例子，說明如何以上列三種方式表示演算法。,2

10、2,歐幾里德演算法(輾轉相除法),歐幾里德演算法大約在西元前300年由希臘數學家歐幾里德提出，可用於求出二個整數的最大公因數(GCD,Greatest Common Divisor)，又稱為輾轉相除法。,23,歐幾里德演算法(Euclid Algorithm)以自然語言表示,24,歐幾里德演算法(Euclid Algorithm)以流程圖表示,25,ANSI流程圖符號,26,ANSI流程圖符號(續),27,歐幾里德演算法(Euclid Algorithm)以虛擬碼表示,28,虛擬碼(Pseudo Code),虛擬碼以一種混雜著自然語言與高階程式語言結構的方式來描述演算法。可以達到簡潔易讀、容易

11、分析，而且也容易轉換為高階程式語言的目的。以下我們介紹本課程所採用的虛擬碼撰寫規則，因為虛擬碼仍然具有自然語言性質，因此這些撰寫規則有時可以稍稍調整，以方便閱讀者理解為原則。,29,虛擬碼(Pseudo Code)(續),虛擬碼撰寫規則如下:演算法名稱及參數：以 Algorithm 演算法名稱(參數 1,參數 2,)來列出演算法名稱並指明其輸入參數。輸入：以 Input 輸入描述 來進行輸入說明輸出：以 Output 輸出描述 來進行輸出說明,30,虛擬碼(Pseudo Code)(續),設定：以 表示，可以將一個算式(expression)的值指定給某一個變數(置入某變數中)算術運算：以+/

12、%表示加、減、乘、除、模(除法求餘數)運算,31,虛擬碼(Pseudo Code)(續),比較與邏輯運算：以=表示等於、大於、小於、大於等於、小於等於及不等於的運算，並使用 表示邏輯的且、或與反向的運算。決策結構：以 if 條件 then 條件為真的動作 else 條件為偽的動作 end if 來表示。當條件成立時，演算法執行所有包含在條件為真的動作的所有指令(步驟)；反之則執行所有包含在條件為偽的動作的所有指令。,32,虛擬碼(Pseudo Code)(續),while 迴圈：以 while 條件 do 迴圈動作 end while 來表示。當條件成立時，演算法會重複執行所有包含在迴圈動作的

13、所有指令；反之則離開迴圈，進入下一個指令。for 迴圈：以 for 迴圈變數變動之範圍及其變動方式do 迴圈動作 end for 來表示。當迴圈變數的值在指定的範圍中時，演算法會重複執行所有包含在迴圈動作的所有指令；反之則離開迴圈，進入下一個指令。,33,虛擬碼(Pseudo Code)(續),陣列元素索引：以 陣列名稱 i 代表命名為陣列名稱的陣列索引(index)為 i 的元素，一個有 n 個元素的陣列，其元素索引值為 0,1,n-1演算法呼叫：以 演算法名稱(參數)來表示演算法的呼叫演算法返回:以 return 返回值 來代表演算法結束執行並輸出返回值。,34,1.5 如何實作演算法?,

14、35,演算法的實作(implementation),除了以自然語言、流程圖、虛擬碼表示演算法之外，我們也可以使用高階程式語言(high level programming language)來表示演算法。當我們以高階程式語言表示演算法時，我們可以在電腦上直接執行以高階程式語言編寫而成的程式，並藉此得到執行結果。我們特別將之稱為以高階程式語言實作(implement)演算法，或是稱為以高階程式語言進行演算法的實作(implementation)。,36,演算法的實作(implementation)(續),以下我們將舉例說明使用C、C+、Java 與Python 語言實作歐幾里德演算法，或稱為歐幾

15、里德GCD(Euclid GCD)演算法。建議使用Jeep5軟體進行C、C+、Java 與Python 語言的編輯、編譯與執行。Jeep5 為Java Editor for Chinese Programmer v5.0 的簡稱，是由江振瑞教授使用Java 語言所編寫的整合開發環境(Integrated Development Environment,IDE)軟體，支援C、C+、Java 與Python 四種語言，並透過簡潔的中文介面，讓使用者輕易完成四種不同語言程式的編輯、編譯與執行等工作。請參考本單元後的Jeep5補充資料以獲得Jeep5詳細的資訊。,37,演算法的實作(implement

16、ation)(續),因為演算法有指定輸入的特性，因此演算法僅處理特定的輸入。例如，剛剛提過的歐幾里德演算法指定輸入二個正整數m及n。當然，當我們以高階程式語言實作演算法，讓使用者特過輸入介面由外界傳入演算法輸入時，可能會輸入錯誤的資料(例如輸入負數)。本課程聚焦於演算法解決問題的核心概念，因而假設所有的輸入都符合演算法的指定，所以在實作演算法時不處理使用者輸入錯誤資料的狀況。,38,演算法的實作(implementation)(續),在實務上，若我們將符合演算法指定的輸入資料以文字檔案形式儲存，並以作業系統之輸入轉向(redirect)方式將文字檔案資料直接輸入高階程式語言程式中，則所有的輸入

17、都會符合演算法的指定。基本上，著名的計算機協會國際大學生程式設計競賽(Association of Computing Machinery International Collegiate Programming Contest，簡稱 ACM ICPC）就是採取上述的方法作為高階語言程式的輸入方式以進行比賽。ACM ICPC是一個試煉各種演算法實作的好場合，國際間也有許多團體提供相關的ICPC訓練教學網站(例如，UVa Online Judge)與ICPC賽事裁判系統(例如，PC2(Programming Contest Control)系統)。請參考本單元後的補充資料以獲得ACM ICPC詳

18、細的資訊。,39,以C程式語言實作歐幾里德GCD演算法,40,下列的C語言程式EuclidGCD.c以int EuclidGCD(int m,int n)函式或函數(function)實作歐幾里德演算法。並在主要函式main()中加入標準輸入(printf(.)與標準輸出(scanf(.)敘述，並呼叫EuclidGCD方法，讓演算法可以由外部輸入訊息，並輸出計算結果。,以C程式語言實作歐幾里德GCD演算法執行結果,41,實作展示:以Jeep5編輯、編譯及執行執行結果:,以C+程式語言實作歐幾里德GCD演算法,42,下列的C+語言程式EuclidGCD.cpp以int EuclidGCD(int

19、 m,int n)函式實作歐幾里德演算法。並在主要函式int main()中加入標準輸入(cin.)與標準輸出(cout.)敘述，並呼叫EuclidGCD方法，讓演算法可以由外部輸入訊息，並輸出計算結果。,以C+程式語言實作歐幾里德GCD演算法執行結果,43,實作展示:以Jeep5編輯、編譯及執行執行結果:,以Java程式語言實作歐幾里德GCD演算法,44,下列的Java語言程式EuclidGCDClass1.java以方法(method)static int EuclidGCD(int m,int n)實作了歐幾里德演算法。並在主類別EuclidGCDClass1中的主要方法public s

20、tatic void main()中加入標準輸入(Scanner Cin=new Scanner(System.in);.Cin.nextInt()與標準輸出(System.out.print(.)敘述，並呼叫EuclidGCD方法，讓演算法可以由外部輸入訊息，並輸出計算結果。,以Java程式語言實作歐幾里德GCD演算法執行結果,45,實作展示:以Jeep5編輯、編譯及執行執行結果:,以Java程式語言實作歐幾里德GCD演算法(續),46,下列的Java語言程式EuclidGCDClass2.java與EuclidGCDClass1.java類似，但是採用視窗輸入(JOptionPane.sh

21、owInputDialog(.)與視窗輸出(JOptionPane.showMessageDialog(.)敘述，讓演算法可以由外部輸入訊息，並輸出計算結果。另外，程式EuclidGCDClass2.java也善用Java語言支援UTF-8字元編碼的國際化特性，使用中文來替變數命名。這樣做有一個好處，當讀者看到程式中出現中文的變數名稱時，就可以知道這是由使用者自行命名的，而英文的部份則很清楚的是語言的關鍵字或是語言系統中內建的類別。,以Java程式語言實作歐幾里德GCD演算法執行結果(續),47,實作展示:以Jeep5編輯、編譯及執行執行結果:,以Python程式語言實作歐幾里德GCD演算法,

22、48,下列的Python語言程式EuclidGCD.py以EuclidGCD(m,n)方法實作歐幾里德演算法。並以標準輸入(raw_input(.)與標準輸出(print(.)敘述由外部輸入訊息及輸出計算結果。,以Python程式語言實作歐幾里德GCD演算法執行結果,49,實作展示:以Jeep5編輯及執行執行結果:,1.6 演算法的正確性與效能,50,演算法的正確性與效能,一個演算法一定要能夠產生正確的結果，也就是滿足正確性(correctness)，如此演算法才能夠為人們所用。我們可以透過一些證明的技術，如歸納法(induction)或矛盾法(contradiction)等來證明演算法的正確

23、性。演算法的正確性無疑的是演算法最重要的特性，然而因為課程時間有限，我們有時不會特別說明演算法的正確性證明。請大家自行參考文獻資料以獲得演算法的正確性證明。,51,演算法的正確性與效能(續),除了演算法的正確性之外，我們也關心演算法的效能(efficiency)，也就是討論演算法是否能夠使用較少資源而有效率地執行。演算法執行時使用的資源有:時間資源記憶體資源網路頻寬資源(當演算法需要透過網路傳輸資料時)邏輯閘資源(當演算法使用邏輯閘實作時)在本課程我們聚焦於討論演算法執行時使用的時間資源與記憶體資源。,52,演算法的正確性與效能(續),若我們能夠將所有的演算法以相同的高階程式語言實作，並在相同

24、條件下於相同的電腦上執行，則我們似乎可以利用高階程式語言程式的執行時間與執行時所佔用的記憶體空間來衡量被實作演算法的效能。不過，這太不實際了，而且藉由這個方式我們也難以直接看出演算法效能與演算法輸入規模(input size)的關係。我們需要其他更具學理基礎，而且更容易分析與比較的方式來衡量演算法的效能,53,演算法的正確性與效能(續),在學理上，我們使用:時間複雜度(time complexity)空間複雜度(space complexity)來分析演算法的執行時間與佔用的記憶體空間。以下我們先說明演算法的時間複雜度概念，而演算法空間複雜度則是類似的概念，我們在稍後演算法複雜度分析範例時會一

25、併說明。,54,1.7 演算法的時間複雜度,55,演算法的時間複雜度,演算法的時間複雜度分為以下三種狀況：最佳狀況(best case)時間複雜度:考慮演算法執行時所需要的最少執行步驟數。最差狀況(worst case)時間複雜度:考慮演算法執行時所需要的最多執行步驟數。平均狀況(average case)時間複雜度:考慮所有可能狀況下演算法執行時所需要的平均步驟數。在上列的定義中，所謂的一個步驟(step)指的是演算法中的基本操作(operation)，如算術運算操作(arithmatic operation)及邏輯運算操作(logic operation)等。有時候我們也會將幾個連續執行的

26、操作視為一個步驟，我們稍後會有詳細的說明。,56,演算法的時間複雜度(續),在所有的時間複雜度之間，最差狀況時間複雜度是很重要的一項。一般我們會先分析演算法的最差狀況時間複雜度，因為這項複雜度可以讓我們了解演算法在最壞的情況下的執行時間概況。例如，假設我們需要使用一些天氣預測演算法來預測三天後的天氣慨況，並在一小時之後發佈預測結果。姑且不論演算法預測天氣的準確度，若我們能夠分析出這些演算法的最壞情況時間複雜度，則大約可以推估出哪些演算法即使在最壞情況下也可以在一小時之內執行完畢，讓我們來得及發佈天氣預測結果。,57,演算法的時間複雜度(續),針對一些我們平日經常使用的演算法，會面臨各種不同狀況

27、，執行步驟有時多有時少，而碰到最壞與最好狀況的機率又很低，則此演算法的平均狀況時間複雜度也很重要。例如，我們經常使用排序(sorting)演算法將一連串的雜亂數字依由小到大的次序排好順序，或將一連串的雜亂檔案名稱依照字典順序(lexical order，如字典版將單字由A開頭排到Z開頭的順序)排列。因為可能面對不同的一連串數字與檔名，因而此時我們最關心排序演算法的平均時間複雜度。,58,演算法的時間複雜度(續),相對於最差狀況時間複雜度與平均狀況時間複雜度，演算法的最佳狀況時間複雜度則顯得較不重要。這是因為一方面最佳狀況出現的機率不高，而另一方面則是因為有時最佳狀況時間複雜度是顯而易見的(tr

28、ivial)。例如，我們直接利用質數(prime number or prime)的定義設計一個演算法，檢查一個輸入的大於2的正整數n是不是質數。依照定義，我們只要由整數2開始到n之間(不含n)找到任何一個n的因數(factor)，就可以判斷n不是質數了。對於這個演算法，若我們輸入任何大於2的偶數n，都可以馬上找出2是n的因數而判斷n不是質數，這對應演算法的最佳狀況時間複雜度，這顯然是顯而易見的。,59,演算法的時間複雜度(續),一般而言，演算法的平均狀況時間複雜度最難分析(求出)，最壞狀況時間複雜度稍微容易些，而最佳狀況時間複雜度最容易分析。我們通常會分析演算法的最壞狀況時間複雜度，若有可能

29、，還會分析演算法的平均狀況時間複雜度，但是常常不分析最佳狀況時間複雜度。,60,演算法的時間複雜度(續),一個檢查大於2正整數是否為質數的演算法,61,演算法的時間複雜度(續),針對PrimeCheck1演算法，我們可以看出:輸入大於2 的任意正整數n，若n 是質數，則演算法PrimeCheck1 需要執行整數除法求餘數(也就是n%i)操作與整數比較(也就是(n%i)=0)操作各n-2 次，才可以知道n 是質數。另外，若n 不是質值，則演算法PrimeCheck1 只要執行整數除法求餘數操作與整數比較操作1 次就可以知道n 不是質數。因此，我們很容易看出來，在最壞狀況下，演算法PrimeChe

30、ck1 的執行時間與輸入的正整數n 成正比；而在最佳狀況下，演算法PrimeCheck1 的執行時間大約為執行1次整數除法求餘數與整數比較操作，而與輸入的正整數n 大小無關。也就是說，演算法PrimeCheck1 的最差狀況時間複雜度為n 2，而演算法PrimeCheck1 的最佳狀況時間複雜度為1。至於演算法PrimeCheck1 的平均狀況時間複雜度分析比較複雜，在此我們省略不提。,62,1.8 大O趨近記號,63,趨近記號,一般我們使用趨近記號(asymptotic notation)表示演算法的複雜度(complexity)。趨近記號考慮演算法在處理資料範圍或輸入規模(input si

31、ze)或問題規模(problem size)足夠大時的複雜度。使用趨近記號原因之一為聚焦於輸入規模足夠大的狀況:一般而言，在演算法的輸入規模較小時，不管是有效率(複雜度較低)或沒有效率(複雜度較高)的演算法通常都可以很快的執行完畢。相對的，在演算法的輸入規模非常大時，有效率的演算法還是可以在一定的時間內執行完畢，而沒有效率的演算法則可能需要相當長的時間，甚至於需要經年累月才能結束。因此，在分析演算法時，我們會聚焦於演算法輸入規模足夠大的狀況，這是為什麼分析演算法複雜度需要採取趨近記號的原因之一。,64,趨近記號(續),使用趨近記號原因之二為簡化個別步驟認定:當我們分析演算法時，認定不同的個別步

32、驟經常會產生不同的時間複雜度。例如，當我們將演算法PrimeCheck1中的整數除法求餘數操作與整數比較操作視為一個步驟時，我們說演算法PrimeCheck1的最差狀況時間複雜度為n-2。當我們將整數除法求餘數操作與整數比較操作視為二個個別步驟時，我們說演算法PrimeCheck1的最差狀況時間複雜度為2n-4。而當我們另外將迴圈控制中的迴圈變數遞增與迴圈變數與迴圈結束值的比較再視為另外二個個別步驟時，則我們可以說演算法PrimeCheck1的最差狀況時間複雜度為4n-8。以上這些時間複雜度的說法，似乎都正確。當我們使用趨近記號來表示演算法複雜度的情況下，這些說法是完全相通的；更精確地說，它們

33、使用趨近記號來表示時是完全相同的。這簡化個別步驟的認定，是我們使用趨近記號來表示演算法複雜度的原因之二。,65,趨近記號(續),在演算法處理資料範圍或輸入規模足夠大時，演算法的執行時間複雜度會趨近於一個量級(order)。一般而言，演算法的執行時間複雜度是一個輸入規模n的多項式，當演算法輸入規模足夠大時，時間複雜度多項式中除了最高次方的項目外，其他的部分都可以被忽略；而同時，最高次方項目的常數係數也同時可以被忽略。,66,趨近記號(續),例如，若一個演算法的時間複雜度為n-2、2n-4或4n-8，則當n足夠大時，此演算法的時間複雜度趨近於n，屬於一次方或線性(linear)量級。又例如，若一個

34、演算法的時間複雜度為35n2+12n+11，則當n足夠大時，此演算法的時間複雜度趨近於n2，屬於平方(quadratic)量級。而若一個演算法的時間複雜度為28n3+1245n2+162n+321，則當n足夠大時，此演算法的時間複雜度趨近於n3，屬於立方(cubic)量級。一般而言，若是一個演算法的時間複雜度表示為一個多項式，則我們取這個多項式的最高次方為其時間複雜度的量級，並且將此量級以大O記號表示。以下我們詳細介紹大O記號。,67,大O記號,大O記號(Big-O notation)為一種趨近記號，我們通常使用大O記號來表示演算法在輸入規模足夠大時，其複雜度的量級趨近情形，以下我們正式定義大

35、O記號：定義 大O記號(Big-O notation):(O 代表order 之意)令f(n)與g(n)是由非負整數對應至實數的函數，若存在正實數常數c 和正整數常數n0，使得對所有的n n0 而言，f(n)cg(n)成立，則我們說f(n)=O(g(n)。因為O(g(n)帶有集合的涵義，因此f(n)=O(g(n)唸作f(n)屬於Big-O of g(n)；而比較比較完整的英文唸法為f of n is of Big-O of g of n)。,68,大O記號(續),例如，令f(n)=2n2+n+3，g(n)=n2。因為存在c=6 和n0=1，使得當n n0=1 時，f(n)=2n2+n+3 cn

36、2=6n2=6g(n)成立，所以我們說f(n)=2n2+n+3=O(g(n)=O(n2)。我們可以由圖看出，當n n0=1 時，f(n)6g(n)成立，我們稱g(n)是f(n)的趨近上界(asymptotic upper bound)。這表示g(n)的成長率比f(n)還快或一樣快。,69,一些複雜度的大 O 記號表示及其量級,70,1.9降低演算法時間複雜度量級,71,演算法時間複雜度量級比較,我們首先比較不同演算法時間複雜度在各種不同量級之下的執行步驟數。某些量級在演算法的輸入規模還不是很大的情況下，演算法時間複雜度的對照數值(執行步驟數)就已經相當大了，這表示演算法需要執行相當久的時間。例

37、如，若演算法的一個步驟(如比較兩個整數的操作)需要一個微秒(s,micro section，百萬分之一秒)來完成，則當輸入規模n 為32 時，平方量級演算法需要1,024 微秒0.001 秒來完成，而指數量級演算法需要2n=4,294,967,296 微秒143 分鐘來完成。,72,演算法時間複雜度量級比較(續),演算法時間複雜度量級高低的次序(靠左邊的量級是比較低，成長比較慢的量級)：O(1)，O(log n)，O(n)，O(n)，O(n log n)，O(n2)，O(n3)，O(2n)設計一個時間複雜度量級比較低的演算法是我們必須一直擺在心中的目標。,73,測試質數的一個觀察,以下，我們再

38、舉檢查一個正整數是否為質數的演算法為例，來看看演算法的量級對執行時間的影響。利用以下的觀察，我們可以設計出一個量級比直接使用質數定義設計的演算法的量級更低的演算法。觀察對於任意的大於2 的整數n 而言，若所有小於或等於n 的整數(1 除外)都無法整除n，則n 是一個質數。,74,觀察實例,每個整數n的因數都是成對出現的，例如，16的因數為1與16(116=16)、2與8(28=16)、4與4(44=16)。成對出現的因數中，一個會小於等於n的平方根，而另一個則是大於等於n的平方根，因此，我們只要檢查小於等於n的平方根的所有不等於1的整數中是否有n的因數就可以知道n是不是質數了。,75,另一個用

39、以測試質數的演算法,我們根據上列觀察設計出另一個演算法PrimeCheck2,76,質數檢查演算法複雜度量級比較,最差狀況(worst case)時間複雜度:PrimeCheck1:n-2=O(n)，屬於線性量級。PrimeCheck2:n 1=O(n)，屬於平方根量級。最佳狀況(best case)時間複雜度:PrimeCheck1:1=O(1)，屬於常數量級。PrimeCheck2:1=O(1)，屬於常數量級。在最差狀況下，平方根量級的演算法PrimeCheck2的執行步驟數將比線性量級的演算法PrimeCheck1的執行步驟數少很多。例如，若輸入的n 為2147483647，則演算法Pr

40、imeCheck1 需要執行n-2=2147483645次整數除法求餘數和整數比較敘述才可以得知2147483647是質數，而演算法PrimeCheck2只要執行n-1=46339次，二者的差距約為n=46340 倍。當然，當所輸入的n越大時，這種差距越大。,77,以Java程式語言實作PrimeCheck1演算法,78,下列的Java語言程式PrimeCheck1.java實作PrimeCheck1演算法，並使用System.currentTimeMillis()測量程式執行時間:,PrimeCheck1.java執行結果,79,以Java程式語言實作PrimeCheck2演算法,80,下列

41、的Java語言程式PrimeCheck2.java實作PrimeCheck2演算法，並使用System.currentTimeMillis()測量程式執行時間:,PrimeCheck2.java執行結果,81,1.10演算法複雜度分析範例,82,演算法複雜度分析範例,在本單元中，我們以氣泡排序(bubble sort)與插入排序(insertion sort)演算法為例，再一次演示演算法的複雜度分析。所謂排序(sorting)是將一系列的元素(資料)依照某種順序排列的程序。例如，若元素為數值，則排序將依元素數值的大小以由小而大或由大而小的數值順序(numerical order)排列；又例如，

42、若元素為字串，則排序將依字串的字典順序(lexical order)排列。在本單元中，我們針對一個元素為數值的陣列，說明氣泡排序與插入排序演算法如何將陣列元素依由小而大的數值順序排列。然後我們針對這二個演算法的時間複雜度、空間複雜度進行分析與比較。,83,氣泡排序演算法,氣泡排序(bubble sort)演算法又稱為下沉(sinking)排序演算法或交換(exchange)排序演算法。因為它的執行步驟中每回合(pass)會找出目前未處理過資料中最大的一個，就如同讓最大的氣泡先由水中冒出，然後再讓第二大的氣泡冒出，.，因此稱為氣泡排序演算法。因為它在執行步驟中，如同每回合會讓最重的東西往下沉，然

43、後再讓第二重的東西往下沉，.，因此稱為下沉排序演算法。因為它的執行步驟為不斷的比較並交換兩個相鄰的資料，因此又稱為交換排序演算法。,84,氣泡排序演算法(續),假設我們現在要使用氣泡排序演算法來將陣列中的n 個元素或資料(索引為0,.,n 1)依照其值以由小而大的次序排列其做法為持續兩兩比較相鄰資料，若前一筆(左邊)資料的值大於後一筆(右邊)資料的值，則將此二筆資料互相交換，否則資料的位置即維持不動。上述的比較及交換過程一直持續進行到最後一筆資料被比對到為止，這稱為一個回合(pass)。第一個回合的比對進行到最後一筆資料為止(n 1 次比對)，此時具最大值的資料已經調換至最後(最右邊)的位置了

44、；而第二回合的比對則進行到倒數第二筆資料為止，此時具第二大值的資料已經調換至倒數第二個位置了；其餘依此類推。當進行完第n 1 個回合(比較索引為0 與1 的資料)之後，則所有的資料均已依由小到大的次序排列好了。,85,氣泡排序演算法(續),86,氣泡排序演算法(續),我們舉以下的實例來看看氣泡排序的運作情形：假設有一個陣列具有 5 個元素 8、5、8、6、7，索引為 0,.,4，其中 8 與 8二個元素的值都是 8，但是為了區別起見，我們將之標示為 8 與 8。此陣列經由氣泡排序法排序的過程如下頁圖所示。其中加垂直線的方格代表索引變數 i 所指的元素，而加水平線的方格代表索引變數 j 所指的元

45、素。,87,氣泡排序演算法(續),88,氣泡排序演算法(續),在整個氣泡排序演算法的過程中，8與8的相對位置一直保持不變，也就是8一直排列在8之前。當一個排序演算法能夠讓具有相同值的元素維持原來的相對位置時，我們稱這種排序演算法為穩定(stable)排序演算法。若我們所排序的元素只是一個資料庫的鍵值(key)，則穩定排序演算法在排序之後可以保持所有紀錄原來的次序，這是非常有用的功能。例如，我們可以先針對學生成績資料庫先依國文成績由高到低排序，之後再依總成績由高到低排序。此時資料庫資料的排列次序為總分高的在前，而總分相同的則由國文成績高的排在前面。,89,氣泡排序演算法(續),除了幾個索引變數之

46、外，氣泡排序演算法不需要額外的記憶體空間來輔助排序的進行。不需要額外記憶體空間的排序演算法稱為就地(in place)演算法。這也是很好的特定，這表示氣泡排序演算法的空間複雜度可以視為是常數的(也就是O(1)，而與所需要排序的陣列的大小無關。,90,氣泡排序演算法(續),91,插入排序演算法,以下我們介紹插入排序(insertion sort)演算法。假設我們想要使用插入排序演算法將一個陣列中的元素依照其值由小而大排列，其做法是從第二個元素開始，先以其為處理對象，並向前比對每一個元素以找出其適當插入位置；然後以第三個元素為處理對象，並向前比對每一個元素以找出其適當插入位置，.。這類似我們在交考

47、卷時的一種排序概念：每位學生寫完考卷時就交上自己的考卷；而老師為了方便讓考卷依座號的次序由小到大排序，在每個學生交上考卷時即在已經交上的考卷中從頭到尾(或從尾到頭)找出新交考卷的適當位置插入。在老師手上的考卷永遠都是依座號的次序由小到大排列，而當所有學生都交出考卷時，所有的考卷就已經依座號的次序由小到大排序完畢了。,92,插入排序演算法(續),以下為插入排序(insertion sort)演算法。,93,插入排序演算法(續),我們舉以下的實例來看插入排序演算法的運作過程：假設有一個陣列具有5個元素8、5、8、6、7，索引(index)為0,.,4，其中8與8二個元素的值都是8，但是為了區別起見

48、，我們將之標示為8與8。此陣列經由插入排序演算法排序的過程如下頁之圖所示,94,插入排序演算法(續),95,插入排序演算法(續),在整個插入排序演算法的執行過程中，8 與 8的相對位置一直保持不變，因此插入排序演算法也是一個穩定(stable)排序演算法。除了幾個索引變數與一個陣列數值臨時儲存變數之外，插入排序演算法不需要額外的記憶體空間來輔助排序的進行，因此插入排序演算法也是一個就地(in place)演算法，其空間複雜度為 O(1)。,96,插入排序演算法(續),97,插入排序演算法(續),資料已經由小到大排好的情況下為最佳狀況，在這種情況下，所有的mi=0(1 i n1)，因此我們有M=2(n1)=2n2=O(n)。當資料為反向的由大到小排列時為最差狀況，在這種情況下，m1=1;m2=2;mn-1=n 1，或者我們寫為mi=i(1 i n 1)，因此我們有M=n(n-1)/2+2(n 1)=O(n2)。,98,插入排序演算法(續),99,氣泡排序與插入排序演算法比較,100,The End,101,