跳去內容

複雜度類別

出自維基百科,自由嘅百科全書

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

概論

[編輯]

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

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

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

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

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

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

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

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

睇埋

[編輯]

[編輯]
  1. Complexity Classes (PDF). Chapter 27 of the forthcoming CRC Handbook on Algorithms and Theory of Computation.
  2. Johnson, D. S. (1990). A catalog of complexity classes. In Algorithms and complexity (pp. 67-161). Elsevier.
  3. 3.0 3.1 3.2 Complexity Classes P and NP (PDF). MATH 3220.
  4. NP-complete problem. Encyclopedia Britannica.