演算法分析
演算法分析（粵拼：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.0 1.1 1.2 Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press.
- ↑ 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.
- ↑ Knuth, Donald (1998). Sorting and Searching. The Art of Computer Programming. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional.
