演算法熵

曼德博集合碎形當中嘅一橛

演算法熵，又叫柯爾莫哥洛夫複雜度（英文：Kolmogorov complexity ），數學符號係 K，係理論電腦科學同相關領域上嘅指標，用嚟量度物件有幾複雜。某物件嘅演算法熵，係指要產生嗰件物件嘅程式，最短嘅可能長度。

好似係文頭呢幅圖噉。幅圖像係用曼德博集合產生嘅碎形。如果想要電腦記住呢幅圖，可以有兩個方法：一係叫電腦好似傳統嘅點陣圖噉，記住幅圖每一點係乜嘢色，如果用 24-位元色嚟記嘅話，成幅圖需要用成 1,620,000 個位元組至記得到；另一方面，部電腦又可以記住產生幅圖嘅算式，用家想睇幅圖嗰陣，即場用記住嘅算式砌返幅圖出嚟而呢種做法花嘅位元組數量會細好多－幅圖嘅演算法熵會遠遠細過 1,620,000 個位元組。

概論

睇埋：複雜同演算法

演算法熵可以用嚟比較唔同物件嘅複雜度。舉兩個簡單嘅例子，想像以下呢兩串符號：

1. abababababababababababababababab
2. 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

呢兩串符號長度一樣，但喺複雜度上就相當唔同：串 1 可以描述為將 ab 寫 16 次，即係（當中 se2 係粵語寫嘅意思）

se2 ab 16 times

噉嘅碼－呢段碼淨係用咗 17 個符號；相比之下，串 2 冇咩明顯嘅規律可言，唔能夠用一句語句簡單描述晒，所以要叫電腦死記住

se2 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

呢段碼有成 38 個符號。所以可以話假如用演算法熵做準嘅話，串 1 簡單過串 2。

睇埋

• 運算複雜度
• 認知複雜度

文獻

• Brudno, A. (1983). "Entropy and the complexity of the trajectories of a dynamical system". Transactions of the Moscow Mathematical Society. 2: 127–151.
• Li, Ming; Vitányi, Paul (1997). An Introduction to Kolmogorov Complexity and Its Applications. Springer. ISBN 978-0387339986.