大 O 符號

(由大O符號跳轉過嚟)

O 符號粵拼daai6 ou1 fu4 hou2英文big O notation)係演算法分析上成日用嘅一種符號,攞嚟表示一隻演算法嘅運算複雜度[1]:1.1.3

概論

編輯

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

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

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

 

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

  •   係 10,隻演算法頂攏要行 10 步,或者頂攏要行 10   咁多步(  係個正嘅常數);
  •   係 10,000,隻演算法頂攏要行 40,000 步,或者頂攏要行 40,000   咁多步;

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

 

假設每一步消耗嘅時間都一樣係   咁長,噉隻演算法行起上嚟要消耗嘅時間(時間複雜度)就可以輕易計到出嚟。

算法分類

編輯

電腦科學工作會分析嘅演算法,可以按複雜度分做[1][4]

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

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

 

細 o 符號

編輯

細 o 符號(little o):「  」(「   嘅細 O」)意思係指   增長得快過   好多。

大 omega 符號

編輯

註釋

編輯
  1. 不過要留意嘅係,喺定義   之前,首先要界定啲 input 係「以咩方式表示」嘅-例如 input 嘅數「用二進制十進制表示」。

睇埋

編輯
  1. 1.0 1.1 1.2 Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press.
  2. 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.
  3. 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.
  4. Knuth, Donald (1998). Sorting and Searching. The Art of Computer Programming. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional.