大 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 軸就係 ;隨住 數值升 會跟住升,而「唔同款嘅複雜度」就可以想像成「唔同形狀嘅線」-

Comparison computational complexity.svg

細 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.

[編輯]