運算複雜性理論

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

運算複雜度

內文:運算複雜度

運算複雜性理論最重視嘅運算複雜度指標有兩個[1]

表示方法

睇埋:大 O 符號

喺分析一個演算法嘅複雜度[註 1]嗰陣,電腦科學家會將時間複雜度同空間複雜度表達做輸入嘅大細嘅函數,即係話一個演算法嘅時間複雜度同空間複雜度通常寫成類似噉嘅樣(大 O 符號;big O notation):O(n log n),當中 n 係個輸入嘅大細(例:如果個輸入係個數字,n 會係佢有幾多個位),O(n log n) 反映個演算法要行嘅步嘅數量隨 n 嘅變化,而 T(n log n) 就係實際行要花嘅時間隨 n 嘅變化。例如如果話一個演算法用嘅時間(以秒計)係 T(n log n) ,而 n 表示個輸入有幾多個位:

  • n 係 10,用嘅時間係 10 秒;
  • n 係 10,000,用嘅時間係 40,000 秒

... 如此類推[1]

舉個簡單例子說明,想像而家電腦科學家想諗個演算法出嚟,解決「俾一柞數字個程式,搵吓柞數字當中有冇某一個特定數字」;最原始嘅演算法係將柞數字逐個逐個睇一次,比較吓個數字同個目標數字係咪一樣,用虛擬碼表達嘅話如下:

for i : 1 to length of A
    if A[i] is equal to x
        return TRUE
return FALSE

用呢種做法嘅話,最壞情況係每次要搵數字嗰陣,都要耖足嗮成柞數先俾到答案(答案係「有定冇」),所以呢個演算法嘅最壞情況(worst-case scenario)時間複雜度就係 n 個單位嘅時間,當中 n 代表輸入嗰柞數字入面有幾多個數字,而單位時間代表耖一個數字要用嘅時間[2]

喺電腦科學上,對唔同嘅演算法作出運算複雜度分析好有用:一般認為,一個好用嘅演算法理應能夠喺不損準確性嘅情況下,盡可能用最少嘅時間同空間嚟達成任務-所以對研究演算法嘅電腦科學家嚟講,時間複雜度同空間複雜度都係有用嘅指標,可以攞嚟量度一個演算法有幾好用[3][4]

難解問題

難解問題(intractable problem):指一條理論上可以解決,但實際上冇可能係夠短嘅時間內解嘅問題,即係例如一條運算問題理論上係解到嘅,但要解決條問題需要嗰個演算法極複雜,複雜到就算用最先進嘅超級電腦嚟行,都要行成 100 年先行得-喺實際應用上根本解決唔到[5]

睇埋

註釋

  1. 例:好多電腦科學同相關領域嘅研究都係喺度提出新嘅演算法;而呢啲研究通常都會分析吓個新演算法嘅複雜度,俾人睇到(例如)「個新演算法嘅複雜度低過打前嗰啲演算法,但效用依然係咁好」。

參考

  1. 1.0 1.1 1.2 Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press.
  2. Knuth, Donald (1998). Sorting and Searching. The Art of Computer Programming. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional.
  3. Kolen, J. F., & Hutcheson, T. (2002). Reducing the time complexity of the fuzzy c-means algorithm. IEEE Transactions on Fuzzy Systems, 10(2), 263-267.
  4. Alon, N., Matias, Y., & Szegedy, M. (1999). The space complexity of approximating the frequency moments. Journal of Computer and system sciences, 58(1), 137-147.
  5. Meurant, Gerard (2014). Algorithms and Complexity. p. 4.