| |
|
|
| |
基本程式演算法 |
|
| |
|
|
| |
|
|
| |
甚麼是演算法 |
|
| |
|
|
| |
|
演算法是將原始的資訊，經由一種判斷、數學計算或是歸類準則等，輸出為我們需要的資訊的方法。 |
|
|
| |
|
原始的資訊我們稱之為輸入(Input)，計算、判斷或是歸類的結果，我們稱之為輸出(Output)。 |
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
| |
|
例如圍棋的演算法，輸入了目前的棋步後，經由演算法計算出下一步對應的棋步。 |
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
又例如計算成績的演算法，輸入了各科及所有人的分數後，經由演算法計算出每個人的總分以及排名。 |
|
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
演算法並非程式語言，而可能是一種思考的流程或是數學的方程式，程式語言只是將這樣的思考及處理流程實現出結果的方法之一。如果要使用程式來實現計算分析或是某種功能，我們必須先思考出合適的演算法，再把演算法轉換成程式。 |
|
|
|
| |
|
|
|
|
|
|
|
|
| |
演算法的類別 |
|
| |
|
|
|
|
|
|
|
|
| |
|
基本的演算法 |
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
1. 堆疊 |
|
|
|
| |
|
|
2. 佇列 |
|
|
|
| |
|
|
3. 資料結構 |
|
|
|
| |
|
|
4. 排序 |
|
|
|
| |
|
|
5. 搜尋 |
|
|
|
| |
|
|
6. 求方程式解 |
|
|
|
| |
|
|
|
|
|
|
| |
|
進階的演算法 |
|
|
| |
|
|
|
|
|
|
| |
|
|
1. 方程式計算 |
|
|
|
| |
|
|
2. 統計 |
|
|
|
| |
|
|
3. 濾波 |
|
|
|
| |
|
|
4. 通訊 |
|
|
|
| |
|
|
5. 壓縮 |
|
|
|
| |
|
|
6. 自動控制 |
|
|
|
| |
|
|
7. 視覺 |
|
|
|
| |
|
|
8. 人工智慧 |
|
|
|
| |
|
|
|
|
|
|
| |
時間複雜度與空間複雜度 |
|
| |
|
|
|
|
|
|
| |
|
演算法的好壞，最基本指標有兩個: |
|
|
| |
|
|
|
|
|
|
| |
|
時間複雜度 |
|
|
| |
|
|
時間複雜度的意義是這個演算法的計算有多快。 |
|
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
時間複雜度是用來評斷演算法執行快慢的指標，因為很多的演算法使用在需要高速執行的場合，比方飛彈上用來偵測目標導引飛行方向的演算法，需要很高的計算速度才能準確擊中目標。 |
|
|
|
| |
|
|
很多演算法是要用來進行非常複雜的演算，例如計算氣象資料的演算法就需要很長的時間，因此需要縮減計算的時間。 |
|
|
|
| |
|
|
演算法有多快不是以秒來衡量，而是以計算需要的步驟及次數。 |
|
|
|
| |
|
|
|
|
|
|
| |
|
|
典型的例子是傅立葉轉換(Fourier Transform)，數學上發展出很多種傅立葉轉換的計算方式，如離散傅立葉轉換(Discrete Fourier Transform，簡稱DFT)以及快速傅立葉轉換(Fast Fourier Transform，簡稱FFT)，這兩者需要的計算次數就差異很大，如下表示一個以硬體執行計算的例子，標示出DFT與FFT的計算次數，在執行512個輸入樣本數的情形下，DFT需要262144次的執行次數，FFT則只需要2304次。這表示使用FFT計算時只需要使用DFT時的1/113的時間。 |
|
|
|
| |
|
|
|
|
|
|
| |
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
| |
|
空間複雜度 |
|
|
| |
|
|
空間複雜度的意義這個演算法需要用到的記憶體有多少。 |
|
|
|
| |
|
|
|
|
|
|
| |
|
|
記憶體分為兩種使用的情形，一種是程式本身所佔用的記憶體(ROM)，就是程式碼有多大。另一種是程式執行時，需要使用到的暫存記憶體(RAM)有多大。 |
|
|
|
| |
|
|
在許多的應用場合中，ROM與RAM的大小都有嚴格的限制，很多的控制器中因為只能夠使用成本很低的MPU，所以只有限的記憶體能夠使用，例如冷氣機、遙控器中的MPU。 |
|
|
|
| |
|
|
很多的應用裡，是因為有嚴格的重量限制，例如太空船、飛機，飛彈等，無法裝載太大型的計算機，因此也會限制計算機的計算速度與記憶體大小，因此就需要盡量減少記憶體的使用。 |
|
|
|
| |
|
|
|
|
|
|
| |
|
|
典型的例子也是傅立葉轉換(Fourier Transform)，DFT的計算需要使用到遞迴，在執行512個輸入樣本數的情形下，DFT大約需要使用到(基本變數量)x512的記憶體，FFT則只需要(基本變數量)x2就能夠進行計算，這表示使用FFT計算時只需要使用DFT時的1/256的記憶體 |
|
|
|
| |
|
|
因此僅需要使用小很多的計算機及記憶體，就能夠進行FFT的計算了。 |
|
|
|
| |
|
|
|
|
|
|
| |
Swap數值交換演算法 |
|
| |
|
|
|
|
|
|
| |
|
我們經常需要將兩個數值進行交換的場合，例如在排序中，我們需要改變數值排列的順序，因此需要不斷地在個數值之間進行數值的交換。 |
|
|
| |
|
|
|
|
| |
|
最簡單的排序方法如下圖，依據圖中所示的步驟，便可將兩個數值進行交換。 |
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
| |
Sorting排序演算法 |
|
| |
|
|
|
|
|
|
|
|
| |
|
甚麼是排序演算法 |
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
排序(sorting)，是將一組資料依照使用者需求，予以重新排列其順序。一般會依資料之大小順序排序(由大至小、或由小至大)。排序後之資料，較為容易閱讀、進行統計分析與快速搜尋。 |
|
|
|
| |
|
|
|
|
|
|
| |
|
|
|
|
|
|
| |
|
|
|
|
|
|
| |
|
氣泡排序法(Bubble Sorting) |
|
|
| |
|
|
|
|
|
|
| |
|
|
|
|
|
|
| |
|
|
|
|
|
|
| |
Search搜尋演算法 |
|
| |
|
|
|
|
|
|
| |
|
甚麼是搜尋演算法 |
|
|
| |
|
|
|
|
|
|
| |
|
|
搜尋是在一堆資料中找出所要之特定資料。搜尋時會進襲大量的比較以找到特定的資料，當資料量較少時比較的次數少，很容易能夠尋找到特定的資料，但當資料量龐大時，需要的比較次數就會浪費大量的時間，因此有許多快速搜尋的方法來增加搜尋的效率。 |
|
|
|
| |
|
|
|
|
|
|
| |
|
|
一般資料的搜尋，都是先進行排序後，再使用搜尋法來搜尋特定的資料，排序過後的資料能夠令搜尋效率極高。 |
|
|
|
| |
|
|
|
|
|
|
| |
|
|
|
|
|
|
| |
|
|
|
|
|
|
| |
|
循序搜尋法(Sequential Search) |
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
從第一個資料開始比較是否為欲尋找的特定資料，依序一一比較，直到找到所要尋找的特定資料為止。 |
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
優點 |
|
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
|
程式容易撰寫。 |
|
|
|
|
| |
|
|
|
資料不須事先排序。 |
|
|
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
缺點 |
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
|
搜尋效率比較差(平均次數=(N+1)/2)。 |
|
|
|
|
| |
|
|
|
不管是否有排序，每次都必須要從頭到尾尋找一次。 |
|
|
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
| |
|
二分搜尋法(Binary Search) |
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
二分法是將資料分成兩部份，再將鍵值與中間值比較，如鍵值相等則找到特定資料，小於鍵值時向前半段繼續比較，大於鍵值時則往後半段進行比較，如此，分段比較至尋找到特定資料為止。 |
|
|
|
| |
|
|
|
|
|
|
| |
|
|
優點 |
|
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
|
搜尋效率佳(平均次數=Log2N)。 |
|
|
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
缺點 |
|
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
|
資料必需事先排序。 |
|
|
|
|
| |
|
|
|
檔案資料必需使是可直接存取或隨機檔。 |
|
|
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
| |
|
|
| |
|
|
| |
|
|
| |
|
|
| |
|
|
| |
|
|
| |
|
|
| |
|
|
| |
|
|
| |
|
|
| |
|
|
| |
|
|