【演算】演算法簡介 - Introduction of Algorithm

http://program-lover.blogspot.hk/2008/08/algorithm.html
　　演算法（algorithm）出自於數學用語，指的是：在有限步驟內，解決一個問題的具體步驟和方法。其接受零或多個輸入資料，並在處理過後產生一個以上的輸出結果。

　　經由整理，我們可以知道，演算法必須具備以下特性：

• 有限性（Finiteness）：演算法必須在有限的步驟內完成。
• 有效性（Effectiveness）：演算法中的每個命令都必須為可執行的步驟。
• 正確性（Correctness）：演算法所產生的結果必須是符合預期的。
• 明確性（Definiteness）：演算法中的每個步驟必須是清楚明白、不含糊的。
• 輸入（Input）：由外界提供的零或多筆資料。
• 輸出（Output）：經由處理所得到的一個或多個結果。

換個簡單一點的說法，其實演算法就是所謂解決問題的方法。



　　舉例來說：由於長假閒著無聊，所以你想要打電話給多年未聯絡的的老朋友「郝仁」聊天敘敘舊。但是當你翻開電話簿，發現其中洋洋灑灑百餘個人名，該如何從中找到你想要的電話號碼呢？

　　當然你可以依序，從第一個名字一路找到最後一個。但是，假設電話簿早已依照姓氏筆畫排序，你何不省點功夫？我們可以隨意找到某個位置，若是筆劃比「郝」多一點，我們可以再往前翻一點；若是筆劃比「郝」少一點，我們可以在往後翻一點。直到找到「郝」這個姓氏為止。

　　上述提到的「找電話」，就是我們需要解決的「問題」。而這兩種方法（依序找跟按筆劃找），就是解決「找電話」這個問題的「演算法」（註1）。對於這個問題的「輸入」，就是你希望查到電話號碼的人（郝仁）；而「輸出」理所當然是這個人的電話號碼了。



　　那麼，我們該如何描述我們所使用的演算法呢？

　　我們可以單純的採用文字描述。在上面「找電話」的例子，我用以描述這兩種「找電話」方法的方式就是文字敘述。換句話說，就是使用一般人較能接受的口語來描述演算法。

　　不過，由於用文字敘述容易造成文字太過冗長，且自然語言（如我們所說的語言：中文、英文、日文等，相對於程式語言等「人造語言」）的種類繁多，由不同的人來看可能會產生認知上的差異，而有所誤差。所以此種方式相較之下是比較不精確的。



　　既然用文字描述不太好，我們也可以直接利用實作出來的程式碼描述。如以下以 C 語言實作的「依序找電話」方法：

size_t index = 0;
char name[MAX_NAME_LENGTH];

scanf("%s", name);
while (true)
{
    if (index >= phoneBook.size)
    {
        printf("phone number not found");
        break;
    }

    if (strcmp(phoneBook.record[index].name, name) == 0)
    {
        printf("%s", phoneBook.record[index].phone);
        break;
    }

    index++;
}

　　雖然這種方法不會有文字描述上的「冗長」跟「不精確」等缺點，但是因為這種方式往往需要考量到實作上的細節，也就是針對不同程式語言特性所需的程式撰寫或演算法的修改，使得演算法的描述無法完全專注在實際上的「執行步驟」上。



　　所以，虛擬碼（pseudocode）便為此應運而生了。

　　虛擬碼通常包括類似程式語言的文法和特定的關鍵字，再加上一些較自由的自然語言敘述，可以產生極良好的溝通效果，有助於對程式的瞭解。於是，我們可以將「依序找」的演算法以虛擬碼表示：

Input name
While True do
    If index > phoneBook.size then
        Output "phone number not found"
        Break loop

    If phoneBook.record[index].name = name then
        Output phoneBook.record[index].phone
        Break loop

    index = index + 1

　　除此之外，我們還可以利用工業上經常使用的流程圖（flowchart）來描述演算法。流程圖使用各種標準化的符號、圖形來描述執行步驟與方式。如以下這個「依序找電話」演算法的流程圖範例：



　　相較於文字，顯然這種方式較容易看出演算法的流程，也比文字易懂的多。也因為圖形都經過標準化，因此在解讀上較不會出現解釋歧異的問題。

註1. 實際上，這個「找電話」問題就是典型的搜尋（search）問題，而這兩種尋找電話號碼的方法，則稱為所謂的「搜尋演算法（search algorithm）」。