複雜度類別

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

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

定義上，一款類別會講明三樣嘢^[1]:1.1：

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

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

「

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

」

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

${\displaystyle O(n^{k})}$

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

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

• 運算複雜度

 複雜度類別係電算楔位文，你可以編輯佢充實內容。