運算複雜性理論

出自維基百科,自由嘅百科全書
Jump to navigation Jump to search

運算複雜性理論computational complexity theory)係運算理論嘅一個子領域:喺知道咗一個問題係有可能用電腦解決之後,電腦科學家往往會希望知道要解決呢個問題有幾撈絞-例如想像有個問題,可運算性理論(computability theory)嘅分析顯示佢係有可能用電腦解決嘅,但打後嘅分析發現,解決呢個問題要用嗰個演算法,就算用最先進嘅電腦行都要用(例如)成 100 年先行得完,噉嘅話呢個問題喺實際應用上根本冇得有效率噉解決。對「可以解到嘅問題要嘥幾多時間空間先解到」嘅思考就係運算複雜性理論嘅重心[1]

參考[編輯]

  1. Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press.