複雜度類別

係有關運算複雜度嘅一個概念。

概論

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

定義上，一款類別會講明三樣嘢：
模型－即係話啲問題係用緊乜運算模型嚟解；喺實際應用上，用嘅運算模型通常會係圖靈機，尤其係確定型圖靈機。
問題－「要解嘅問題係乜？要攞咩做 input 同埋畀咩 output 出嚟？」
資源－即係講明「而家呢隻複雜度類別消耗咁多資源？係講緊乜資源？時間定記憶體？」
一款典型嘅複雜度類別，個定義望落會好似以下嘅句子噉：

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

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

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

運算複雜度

攷

運算理論