1.何謂演算法
演算法（Algorithm）是指完成一個計算機的任務，所需要的具體步驟和方法。
給定初始狀態或輸入資料，能夠得出所要求或期望的終止狀態或輸出資料。
2.一個計算機的演算法具有以下的特性：
(1)有限性：
一個處理計算機問題的演算法，必須是在有限步驟內可以結束，也就是不可以存在無窮迴圈 (endless loop) 的可能性。
(2)確定性：
演算法的每一個步驟，針對特定的資料輸入，它執行命令的步驟必須是明確且唯一的定義，最後所得到的結果也必須是明確的。
(3)輸入：
一個演算法必須有明確的輸入，根據資料內容和明確的處理步驟，得到預定的輸出結果。至於實作的部份程式可能只處理固定的資料，不一定要由外面輸入，也就是預設的資料內容。
(4)輸出：
一個演算法至少有一個或一個以上的輸出，它們和輸入有某種特定的關係，任何演算法一定要有輸出，也就是程式執行完畢一定要產生某些結果，沒有輸出結果的演算法是不具意義的。
(5)可行性：一個演算法一定是可行的，例如在合理的時間或是空間需求下，一定可以得到預期的結果。
3.質數 (prime number) 判斷：
質數判斷是計算機科學中很重要的一個問題，假設有一個整數 n，我們要判斷它是否為質數，只要使用 2 ~ n – 2 之間的每一個整數，稱之為 i，如果其中認一個 i 可以整除 n，則 n 不為質數，否則 n 為質數。根據以上想法，用以下幾個明確的步驟來完成：
(1)令整數變數 i 的初值為 2
(2)如果 i 可以整除 n，則 n 不為質數，執行步驟 (6)
(3)將 i 的值加 1
(4)如果 i 的值小於 n，回到步驟 (2)
(5)n 為質數
(6)程式結束
6.質數：
所謂質數 (prime number) 是指除了 1 和本身外，沒有其他任何因數的整數。
7.自然語言形式的演算法：判斷 n 是否為質數
-------------------------------------------------------
input n
n_is_prime = true
For i = 2 to n-1
If n mod i = 0 Then
n_is_prime = false
exit For
EndIf
EndFor
If n_is_prime = true Then
Print n is prime
Else
Print n is not prime
EndIf
-------------------------------------------------------
8.早期的程式設計人員常用流程圖 (flowchart) 的方法，來輔助程式設計，但是這種方法比較適合用於小一點的問題，對於複雜的問題，演算法可能較理想。
EX:
為判斷 n 是否為質數的流程圖
9.在設計一個「好」的演算法，應考慮達到以下目標：
(1)正確性：
所有演算法或者程式，其最低的需求就是可以正確的執行，也就是根據輸入的資料內容，便能得到預期的資料輸出，否則這個演算法或是程式就不具任何意義了。
(2)可讀性：
演算法除了能在機器上正確而快速的執行之外，與相關程式設計師彼此之間的交流也是非常重要的，所以一個好的演算法，一定是方便相關人員的閱讀，如此一來，往後的維護和修改才容易，這包括變數名稱和函數名稱的選取﹑程式語法的流程等等，都要容易理解。
(3)健全性：
正確性的要求是正確的輸入，便有正確的輸出，但是對於部份的使用者而言，並不很清楚何謂正確的輸入，如程式要求輸入數字，但是使用者卻按了字母的情形，所以對於錯誤的輸入，演算法依然可以適當的處理或反應，例如：提示使用者做正確的輸入，而不至於使機器當掉，這就是所謂的健全性。
(4)效率高：
同樣一個問題，可以有很多不同的解法，不同的演算法，所需的時間可能有很大的差別，(EX:一秒和一天的差異)，所以一個好的演算法，其執行的時間效率至少要在使用者的容忍度之內，當然是越快越好。
(5)記憶體需求低：
任何演算法一定有處理的資料對象，資料則一定會佔用記憶體資源，所佔用的空間則越小越好，這牽涉到資料結構和演算法的選擇。
10.演算法的複雜度
利用>>
(1)空間複雜度 (space complexity) >> DRAM-硬體
(2)時間複雜度 (time complexity) >> 程式-軟體
11.程式執行有個特性，就是有非常明顯局部性 (locality)，有實驗數據顯示，「百分之八十的工作，是由百分之二十的程式所完成」
12.迴圈共執行 n 次，也就是其執行次數隨著 n 而改變
--------------------------
s = 0;
for (int i = 0; i < n; i++)
s++;
--------------------------
執行次數與輸入資料成正比
--------------------------
s = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
s++;
--------------------------
則迴圈共執行 n^2 次，也就是執行時將和 n^2 成正比。假設我們以 f(n) 來表示輸入資料量為 n 程式執行所需時間，則前一個程式的 f(n) = n，後一個程式片段的 f(n) = n^2
執行次數與輸入資料值平方成正比
f(n) 總共有四個項目，下表是當 n 的值從 1 到 10000 時，f(n) 和四個項目的值和其分別所佔的百分比：
14.演算法的分析
不同的資料"輸入"，其執行的敘述可能會有很大的差別，所以幾乎不可能事先預測程式執行的"次數"，因此對於演算法的分析，主要都是一種近似性質的"評估"....
15.定義三個和演算法的分析相關的符號： O﹑ W﹑Q，分別讀成大-O﹑大-Omega﹑大-Theta，這三個符號是最常用來作為演算法分析的工具。
沒有留言:
張貼留言