運算複雜度理論

出自維基百科,自由嘅百科全書
(由運算複雜度跳轉過嚟)
跳去導覽 跳去搵嘢

運算複雜度理論wan6 syun3 fuk1 zaap6 dou6 lei5 leon6英文computational complexity theory,CCT)係運算理論嘅一個子領域:喺知道咗一個問題係有可能用電腦解決之後,電腦科學家往往會希望知道要解決呢個問題「有幾撈絞」[1]

基本定位[編輯]

想像叫部電腦程式;個程式出一大拃數做 output。由「撳掣叫部電腦行」至「睇到 output」之間梗會隔咗段可短可長嘅時間-時間複雜度運算複雜度嘅一環。
內文:運算理論
睇埋:複雜度同埋效率

定義上,CCT 研究嘅係運算複雜度:CCT 屬運算理論(theory of computation)嘅子領域;運算理論研究運算數學特性,而 CCT 係呢種研究嘅一部份,旨在想[2]

將解決運算問題所需嘅資源量化[註 1]-同手上每一隻演算法(一隻演算法簡化講即係其中一款『個程式要行嘅步驟』)畀個數值出嚟,表示『用呢段演算法解呢條(或者呢啲)運算問題,會嘥幾多資源』。

舉個具體例子,

想像家陣研究者想寫返個程式,教電腦自動噉計

  • Input:攞兩個數
  • Output:出「 係咪相對質數(coprime;話兩個數係相對質數,指佢哋嘅最大公因數係 1)」,係嘅話畀 TRUE 否則就畀 FALSE [註 2]

最夾硬嚟嗰種方法解呢條問題嘅話,可以教部電腦做[註 3][3][4]

  1. 做 1;
  2. 計吓 能唔能夠畀 整除
  3. z++(將 數值提升 1);
  4. 做到 或者 為止。

最壞情況下,用呢種夾硬嚟嘅做法解條問題,起碼要將步驟 1 至 3 做 當中數值細啲嗰個)次咁多。喺現實世界,電腦要行演算法啲步驟,就最少會到兩種資源

  • 時間-電腦計數快得好交關,好多時就噉睇好似係一瞬間計掂嘅噉,但實際上就算行簡單程式嗰時,部機依然要花一段極短(例如 100 ms)嘅時間嚟行;
  • 記憶體-部機計數就要喺計緊嗰陣記住手上嗰啲數;

CCT 想做嘅,就係攞「解決運算問題嘅演算法」做 input,畀若干個數值做 output,個 output 表示「段演算法消耗嘅資源量有幾多」(運算複雜度),當中以下呢兩種運算複雜度零舍受重視[1][5]

CCT 嘅分析喺應用上好重要:例如想像有條問題,可運算性理論(computability theory)嘅分析顯示佢係有可能用電腦解決嘅,但打後嘅分析發現,解決呢個問題要用嗰段演算法,就算用最先進嘅電腦行都要用成 100 年先行得完,噉嘅話呢條問題喺實際應用上根本冇得有效率噉解決;而且 CCT 仲能夠幫手判斷啲演算法「有幾好」-想像又有條問題,可以攞多隻唔同嘅演算法解決,而 CCT 就夠同每隻演算法畀啲數值出嚟,等電腦科學軟件工程工作者有得客觀噉比較「邊隻演算法比較好」(正常嚟講,假設解問題嘅功效一樣,嘥嘅資源嘅量係愈少愈好)。因為噉,運算複雜度理論畀好多 IT 工作者視為佢哋嗰行必備嘅知識[1]

大 O 符號[編輯]

內文:大 O 符號

好多 IT 應用嘅工作,都涉及分析手上嘅演算法「有幾複雜」,例如家陣有班電腦科學家想提出一隻新嘅演算法,佢哋可以做嘅,就係攞隻新演算法去解問題,跟住又攞舊有嗰啲演算法解,畀人睇到「隻新演算法嘅複雜度低過打前嗰啲演算法,但解問題嗰陣嘅效用依然係咁好」[6][7]。喺實際應用上,佢哋通常會將運算複雜度表達做 input 嘅大細嘅函數,即係[1]:1.1.3

一隻演算法嘅效率可以由一個函數 嚟表示, 會由自然數 ℕ 嗰度計出個數,令 等如『隻演算法對 咁長嘅 input 會做嘅基本作業數量,最大會係幾多』[註 4]

大 O 符號(big O notation)嘅做法就係建基於上面條原則嘅。喺大 O 符號之下,一隻演算法嘅時間複雜度同空間複雜度通常寫成類似噉嘅樣:

當中 係個 input 嘅大細(例如如果個輸入係個數字, 會係佢有幾多個位), 反映隻演算法要行嘅步嘅數量隨 嘅變化,如果隻演算法要行嘅步數等如 ,噉即係話

  • 係 10,隻演算法頂攏要行 10 步;
  • 係 10,000,隻演算法頂攏要行 40,000 步;

... 如此類推。數學化啲噉講,如果話 ,意思即係有個正嘅整數 同正嘅常數 ,並且

假設每一步消耗嘅時間都一樣係 咁長,噉隻演算法行起上嚟要消耗嘅時間(時間複雜度)就可以輕易計埋出嚟。有咗上述嘅思考方式,就可以將啲演算法按複雜度分做[1][8]

  • -隻演算法無論 係幾多,最大複雜度都唔變;
  • -隻演算法嘅複雜度同 線性關係,例如線性搜尋(linear search)就係噉;
  • -隻演算法嘅複雜度同 成線性關係,例如對分搜尋(binary search)就係噉;
  • -隻演算法嘅複雜度同 成線性關係,例如冒泡排序(bubble sort)就係噉[9]

... 呀噉。上述呢啲「唔同款嘅複雜度」可以用下圖噉嘅方式想像:設 做「要行嘅步嘅數量最大係幾多」(),下圖裏面打戙條軸打橫條軸就係 ;隨住 數值升 會跟住升,而「唔同款嘅複雜度」就可以想像成「唔同形狀嘅線」-

Comparison computational complexity.svg

複雜度量度[編輯]

睇埋:演算法分析

要衡量「一段演算法運算複雜度有幾高」,有好多種做法。

時間同空間[編輯]

內文:時間複雜度空間複雜度

時間複雜度(time complexity)係運算複雜度分析上最常用嘅複雜度指標,指緊「段演算法行嗮需要幾耐時間」,時間愈耐段演算法就愈算係複雜。喺實際應用上,一段演算法嘅時間複雜度唔會寫做「實際行段演算法需要幾耐時間」,而係會攞大 O 符號嚟表示[10][11]:Ch. 3

首先,想像將段演算法寫做虛擬碼。設一條陣列 arr,條陣列係段演算法嘅 input 而佢長度係 n 咁多,以下係段演算法嘅其中一橛仔[12]

  statement1;
  statement2;
  statement3;

好似以上嘅「就噉行三行陳述式」嘅碼,無論 n 係幾多都一樣係行一次,所以複雜度係 ,而好似以下噉嘅碼(睇埋 foreach 嘅概念):

   arr 入面嘅每嚿數據,做
    statement4;

上面嘅碼會將 statement4n 咁多次,所以複雜度係 ... 如此類推[12]

空間複雜度(space complexity)係另一個運算複雜度分析上成日用到嘅指標,指「段演算法行嘅期間會霸幾多記憶體」。一般嚟講,任何要攞 input 嘅演算法行嗰陣,都實會霸一定量嘅記憶體-段演算法行嗰陣時,部電腦起碼實要搵啲記憶體記住個 input 嘅值;而除此之外,輔助空間(auxiliary space)亦都會增加一段演算法嘅空間複雜度-輔助空間泛指 input 以外嘅數據霸走嘅記憶體,即係話

段演算法總共霸走嘅記憶體量(空間複雜度反映嘅資訊) = input 霸走嘅記憶體量 + 輔助空間

輔助空間裏面嘅數據,包括個程式會用到嘅非 input 常數變數[11]:Ch. 3

噉講即係話,要檢驗一段演算法嘅時間同空間複雜度,最基本上要䁽吓段演算法嘅碼,並且:

數吓每行碼『要行嘅次數』會點樣隨住 n 而變化(時間複雜度)同埋啲碼『用咗幾多 input 以外嘅常數同變數[註 5]』(空間複雜度)噉。

最好同最壞[編輯]

內文:最好、最壞同平均情況複雜度

最好、最壞同平均情況複雜度係分析演算法複雜度嗰陣成日會講到嘅三個指標[13][14][15]

  • 最好情況(best case,):指段演算法喺「最好」(最慳時間空間)嘅情況下消耗幾多時間空間資源;
  • 最壞情況(worst case,):指段演算法喺「最壞」(最嘥時間空間)嘅情況下消耗幾多時間空間資源;
  • 平均情況(average case):指段演算法喺「平均」嘅情況下要消耗幾多時間空間資源,即係攞嗮所有可能情況,計佢哋平均要消耗幾多時間空間資源;

舉例說明,用線性搜尋演算法做例子:試諗家陣要指定一個 input 數,再由一條 input 陣列度搵個數出嚟,如果陣列入面冇嗰個數,就顯示(例如)「搵唔到」,即係

  • Input
    1. 要摷嗰條陣列,同埋
    2. 想搵嗰個數;
  • Output
    • 想要嗰個數喺陣列嘅第幾個位(好似下圖噉由 0 數起),
    • 如果陣列入面冇嗰個數,就出「搵唔到」噉嘅字。
Array1.svg

要解呢條問題,線性搜尋係最簡單直接嗰種做法-即係將條陣列入面啲數逐個逐個攞嚟睇,搵到就畀嗰個數出嚟做 output,睇完嗮成條陣列都冇就畀「搵唔到」做 output。如果用線性搜尋解決條問題嘅話[14]

  • 喺最好情況下,陣列入面想要嗰個數,而且個數咁啱得咁橋喺正條陣列第一格,所以電腦行 1 步就行完,用符號表達係
  • 喺最壞情況下,陣列入面想要嗰個數,但個數咁啱得咁橋喺正條陣列最尾嗰格,所以電腦行 n 步至行完(n = 條陣列嘅長度),用大 O 符號表達係
  • 平均情況複雜度()就要噉計[註 6]
    ,當中 係指「input 大細 嗰陣,要行幾多步」;

-喺廿一世紀初嘅應用上,最壞情況複雜度一般畀人視為重要資訊,分析演算法嗰時實會睇;相比之下,啲人比較少會留意平均同最好情況複雜度[13]

布林公理[編輯]

複雜度類別[編輯]

內文:複雜度類別

難解問題[編輯]

睇埋:組合性爆發

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

P-NP 問題[編輯]

內文:P-NP 問題

簡史[編輯]

睇埋[編輯]

  • 軟件最佳化
  • 記憶洩漏(memory leak):指個程式攞咗啲記憶體嚟用,但用完之後又冇「放返開」啲記憶體,於是個程式就霸咗一啲佢唔會用嘅記憶體,所以就搞到部電腦有嘅系統資源量不必要噉減少咗。具體啲講,程式嘅源碼入面成日會有類似以下噉嘅碼-
    攞 XXX 呢件資源嚟用;
    將攞到嘅資源做 YYY 噉嘅運算;
    • 好多時,用家仲有必要手動噉加多行碼(類似 delete() 噉),話畀部電腦知「個程式用完 XXX 呢嚿資源喇,嚿資源霸咗嘅記憶體可以空出嚟做第啲嘢」[註 7]。如果用家冇噉做,就會引致記憶洩漏,喺複雜啲嘅軟件當中,記憶洩漏會搞到隻軟件行起上嚟明顯慢咗[17]。到咗廿一世紀初,多人用嘅程式語言或者寫程式架生往往會或多或少噉有垃圾回收-指教部電腦自動噉釋放啲「個程式打後唔再提到」嘅記憶體-或者類似嘅功能[18]
  • 有效方法(effective method):運算理論上嘅一個概念。如果話一個方法係「可以解決運算問題 A 嘅有效方法」,意思即係話用呢個方法解決問題 A 嗰陣[19]
    • 部電腦會行完若干步之後停低。
    • 部電腦實會出到正確嘅答案。
    • 原則上,個步驟可以由一個手上揸住紙筆嘅人做完,而且個人淨係需要跟從個方法啲步驟。
  • 可運算性理論
  • 軟件大細估計
  • 命題邏輯
  • 奧坎剃刀

註釋[編輯]

  1. 假設已經證明咗條問題係可運算嘅
  2. 好似噉嘅問題就係所謂嘅決定問題
  3. 至於點樣有技巧噉解呢條問題,可以睇吓歐幾里得演算法
  4. 不過要留意嘅係,喺定義 之前,首先要界定啲 input 係「以咩方式表示」嘅-例如 input 嘅數「用二進制十進制表示」。
  5. 尤其要留意有冇邊啲常數變數係唔必要嘅。
  6. 假設 每個可能數值出現嘅機率都一樣。睇埋概率分佈嘅概念。
  7. 尤其係 C 或者 C++ 等稍為低階嘅語言嘅子程序

文獻[編輯]

[編輯]

  1. 1.0 1.1 1.2 1.3 1.4 Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press.
  2. An introduction to research in Computational Complexity Theory.
  3. Crandall, R., & Pomerance, C. (2005). Prime Numbers (2nd Ed.), Berlin: Springer.
  4. Agrawal, M., Kayal, N., & Saxena, N. (2004). PRIMES in P. Annals of Mathematics. 2nd Series, 160(2): 781-793.
  5. Cormen, T., Leiserson, C., & Rivest, R. (2005). Introduction to Algorithms (2nd Ed.), Cambridge, Massachusetts: MIT Press.
  6. 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.
  7. 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.
  8. Knuth, Donald (1998). Sorting and Searching. The Art of Computer Programming. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional.
  9. Astrachan, Owen (2003). "Bubble sort: an archaeological algorithmic analysis" (PDF). ACM SIGCSE Bulletin. 35 (1): 1-5.
  10. Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc.
  11. 11.0 11.1 Kuo, W., & Zuo, M. J. (2003). Optimal reliability modeling: principles and applications. John Wiley & Sons.
  12. 12.0 12.1 How to find time complexity of an algorithm?. Adrian Mejia.
  13. 13.0 13.1 0.1 Worst and best case analysis. web.stanford.edu.
  14. 14.0 14.1 Worst, Average and Best Case Analysis of Algorithms. GeeksForGeeks.
  15. Time Complexity Analysis. Medium.
  16. Meurant, Gerard (2014). Algorithms and Complexity. p. 4.
  17. Memory Leak in Python requests. GeeksForGeeks.
  18. Jones, R., & Lins, R. (1996). Garbage collection: algorithms for automatic dynamic memory management. John Wiley & Sons, Inc.
  19. Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Press, 1971.

[編輯]