演算法分析

演算法分析粵拼jin2 syun3 faat3 fan1 sik1英文analysis of algorithms)喺電腦科學上係指搵出演算法(algorithm)嘅運算複雜性(computational complexity;指段演算法要用幾多時間同記憶體等嘅資源嚟行)嘅分析過程:喺思考要點樣設計演算法解決運算問題嗰陣,電腦科學家往往會希望知道要用嘅演算法「有幾撈絞」-舉個例說明,想像有段演算法,第一步嘅分析證明咗段演算法係有可能用電腦行嘅,但打後進一步嘅分析發現,呢段演算法複雜到就算用最先進嘅電腦行,都要用成 100 年先行得完,噉嘅話段演算法喺實際應用上根本冇得有效率噉行-呢類思考就係演算法分析嘅重心[1][2]

喺分析一段演算法嗰陣,電腦科學家主要會考慮時間複雜度(time complexity;指一段運算要用幾多時間嚟解)同空間複雜度(space complexity;指一段運算要用幾多記憶體嚟解)[1],佢哋會將時間複雜度同埋空間複雜度表達成輸入嘅大細嘅函數,即係話一段演算法嘅時間複雜度同空間複雜度通常寫成類似噉嘅樣(大 O 符號;big O notation):O(n log n),當中 n 係輸入嘅大細(例:如果個輸入係個數字,n 會係佢有幾多個位),O(n log n) 反映個演算法要行嘅步嘅數量隨 n 嘅變化,而 T(n log n) 就係實際行要花嘅時間隨 n 嘅變化。例如如果話一個演算法用嘅時間(以秒計)係 T(n log n) ,而 n 表示個輸入有幾多個位:

  • n 係 10,用嘅時間係 10 秒;
  • n 係 10,000,用嘅時間係 40,000 秒

... 如此類推[1]

舉個簡單例子說明,想像而家電腦科學家想諗個演算法出嚟,解決「俾一柞數字個程式,搵吓柞數字當中有冇某一個特定數字」;最原始嘅演算法係將柞數字逐個逐個睇一次,比較吓個數字同個目標數字係咪一樣,用虛擬碼表達嘅話如下:

for i : 1 to length of A
    if A[i] is equal to x
        return TRUE
return FALSE

用呢種做法嘅話,最壞情況係每次要搵數字嗰陣,都要耖足嗮成柞數先俾到答案(有定冇),所以呢個演算法嘅最壞情況(worst-case scenario)時間複雜度就係 n 個單位嘅時間,當中 n 代表輸入嗰柞數字入面有幾多個數字,而單位時間代表耖一個數字要用嘅時間[3]

睇埋

  1. 1.0 1.1 1.2 Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press.
  2. Braatz, R. P., Young, P. M., Doyle, J. C., & Morari, M. (1994). Computational complexity of/spl mu/calculation. IEEE Transactions on Automatic Control, 39(5), 1000-1002.
  3. Knuth, Donald (1998). Sorting and Searching. The Art of Computer Programming. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional.