Algorithm

通常在針對某一問題開發程式時，都會經過下列步驟：

1. 明確定義問題
2. 設計演算法，並評估其執行效率
3. 撰寫程式，並加以測試

當我們使用某種技巧解決一個問題時，會產生一種逐步執行的程序 ( step-by-step procedure )來解決問題，該種逐步執行的程序即稱為解決這個問題的演算法

定義

• 完成特定功能之有限個指令之集合

• 需滿足下列5個性質：

  1. Input: 外界至少提供 ≥ 0 個輸入
  2. Output: Algorithm 至少產生 ≥ 1 個輸出結果
  3. Definiteness (明確): 每個指令必須是 Clear and Unambiguous

     任何人來看都會得到一樣的解讀

  4. Finiteness (有限性): Algorithm 在執行有限個步驟後，必定終止
  5. Effectiveness (有效性): 用紙跟筆即可追蹤 Algorithm 中執行的過程及結果

Pseudocode(虛擬碼)

定義

最常被使用來定義 Algorithm 的工具是pseudocode, 它有可能是部份 English, 部份 Structured Structured Code

pseudocode 沒有任何標準！

• 可以寫得很像英文敘述
• 也可以寫得很像程式語句

演算法的分析

• 若要得知一個演算法解決一個問題有效率的程度，我們必須分析 (Analyze) 該演算法
• 一個 Algorithm 的好壞，通常有兩個評估因子：
  • Space (空間): Space Complexity
  • Time (時間): Time Complexity

時間複雜度 (Time Complexity)

• 一般來說，對一個演算法進行時間複雜度分析就是求得：
  • 在每個不同的輸入大小 (the size of the input) 之下，該演算法所執行的基本運算次數 (how many times some basic operation is done)
• 分析方式:
  • 我們要分析一個演算法的效率，是將該演算法在每個不同的輸入大小之下，所執行的基本運算次數設定成一個函數 ( Function ; 或稱 Time function, Complexity function 亦可) T(n)

Case

• 有許多被設計出來的演算法，當輸入資料的情況不同時，所分析出來的執行次數也有所不同
• 因此，在分析這些演算法的執行次數時，可依據輸入資料的不同情況區分成三個 Case 來加以分析:
  • The worst case (最差情況)
  • The best case (最佳情況)
  • The average case (平均情況)
• 對於上述時間複雜度分析，我們較常進行最差情況與平均情況的分析，而不是最佳情況分析
  • 平均情況分析是很有用的，這是因為它告訴我們：一個演算法在有許多不同的輸入狀況時，總共所花費的時間為何
  • 最差情況分析是很有用的，這是因為它告訴我們：一個演算法執行時間的上限為何
  • 相對來說，最佳情況分析的用處實在不大
• 通常，平均情況比最差情況要難分析(∴ Worst Case 最常被討論)

參考資料

國立聯合大學陳士杰資料結構