演算法分析

演算法分析（粵拼：jin2 syun3 faat3 fan1 sik1；英文：analysis of algorithms）喺電腦科學上係指搵出演算法（algorithm）嘅運算複雜性（computational complexity；指段演算法要用幾多時間同記憶體等嘅資源嚟行）嘅分析過程。

喺思考要點樣設計演算法解決運算問題嗰陣，電腦科學家往往會希望知道要用嘅演算法「有幾撈絞」－舉個例說明，想像有段演算法，第一步嘅分析證明咗段演算法係有可能用電腦行嘅，但打後進一步嘅分析發現，呢段演算法複雜到就算用最先進嘅電腦行，都要用成 100 年先行得完，噉嘅話段演算法喺實際應用上根本冇得有效率噉行－呢類思考就係演算法分析嘅重心。

運算複雜度

内文：運算複雜度

喺分析一段演算法嗰陣，電腦科學家主要會考慮時間複雜度（time complexity；指一段運算要用幾多時間嚟解）同空間複雜度（space complexity；指一段運算要用幾多記憶體嚟解），佢哋會將時間複雜度同埋空間複雜度表達成輸入嘅大細嘅函數，即係話一段演算法嘅時間複雜度同空間複雜度通常寫成類似噉嘅樣（大 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 秒

... 如此類推。

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

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

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

睇埋

• 演算法
• 運算複雜度理論