複雜度類別

複雜度類別fuk1 zaap6 dou6 leoi6 bit6（英文：complexity class）係有關運算複雜度嘅一個概念。

概論

睇埋：運算複雜度

複雜度類別有好多款，一款複雜度類別會係一個集，包含一拃喺時間或者空間複雜度上相似嘅運算問題。

定義上，一款類別會講明三樣嘢：

1. 模型－即係話啲問題係用緊乜運算模型嚟解；喺實際應用上，用嘅運算模型通常會係圖靈機，尤其係確定型圖靈機。
2. 問題－「要解嘅問題係乜？要攞咩做 input 同埋畀咩 output 出嚟？」
3. 資源－即係講明「而家呢隻複雜度類別消耗咁多資源？係講緊乜資源？時間定記憶體？」

一款典型嘅複雜度類別（暫且嗌佢做 X），個定義望落會好似以下嘅句子噉：

「

X（呢個類別）包嗮所有可以由一部確定型圖靈機（模型）喺 $f(n)$ 咁多時間內（資源）解開嘅決定問題（問題）。

」

例如 P 類別可以算係最簡單嗰隻複雜度類別，包嗮所有可以由一部確定型圖靈機（模型）喺多項式時間（polynomial time）之內（資源）解開嘅決定問題（問題）－當中「多項式時間」意思係指段演算法「要行幾耐先解得到」嘅上限係

$O(n^{k})$

咁多，當中 $k$ 係某個正嘅常數。P 類型嘅問題可以算係「能夠有效噉解」嘅問題，例如「攞個數做 input，判斷個數係唔係質數」（質數判定）就係一條 P 型問題。

除咗 P 之外，複雜度類別仲有好多種進階類型，例如 NP 噉：NP 包嗮所有可以由一部非確定型圖靈機（模型）喺多項式時間內（資源）解開嘅決定問題（問題）；解 NP 型問題嘅演算法可以喺多項式時間內「判定佢搵到嗰個答案係咪正確」－簡化講，即係話呢啲問題「難以有效率噉樣解決，不過是但攞一個 output，可以相對容易噉檢驗個 output 係咪正確答案」。

睇埋

• 運算複雜度