大 O 符號

大 O 符號（粵拼：daai6 ou1 fu4 hou2；英文：big O notation）係演算法分析上成日用嘅一種符號，攞嚟表示一隻演算法嘅運算複雜度。

概論

睇埋：運算複雜度理論

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

「

一隻演算法嘅效率可以由一個函數 $T$ 嚟表示，$T$ 會由自然數 ℕ 嗰度計出個數，令 $T(n)$ 等如『隻演算法對 $n$ 咁長嘅 input 會做嘅基本作業數量，最大會係幾多』。

」

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

$O(n\log n)$

當中 $n$ 係個 input 嘅大細（例如如果個輸入係個數字，$n$ 會係佢有幾多個位），$O(n\log n)$ 反映隻演算法要行嘅步嘅數量隨 $n$ 嘅變化，例如：

• 當 $n$ 係 10，隻演算法頂攏要行 10 步，或者頂攏要行 10 $\times c$ 咁多步（$c$ 係個正嘅常數）；
• 當 $n$ 係 10,000，隻演算法頂攏要行 40,000 步，或者頂攏要行 40,000 $\times c$ 咁多步；

... 如此類推。數學化啲噉講，如果話 $f(n)=O(g(n))$，意思即係有個正整數 $n_{0}$ 同正常數 $c$，並且

$\forall n\geq n_{0},f(n)\leq c\times g(n)$

假設每一步消耗嘅時間都一樣係 $t_{0}$ 咁長，噉隻演算法行起上嚟要消耗嘅時間（時間複雜度）就可以輕易計到出嚟。

算法分類

電腦科學工作會分析嘅演算法，可以按複雜度分做：

• $O(1)$－隻演算法無論 $n$ 係幾多，最大複雜度都唔變；
• $O(n)$－隻演算法嘅複雜度同 $n$ 成線性關係，例如線性搜尋（linear search）就係噉；
• $O(\log n)$－隻演算法嘅複雜度同 $\log n$ 成線性關係，例如對分搜尋（binary search）就係噉；

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

細 o 符號

細 o 符號（little o）：「$f(x)$ 係 $o(g(x))$」（「$f(x)$ 係 $g(x)$ 嘅細 O」）意思係指 $g(x)$ 增長得快過 $f(x)$ 好多。

睇埋

• 運算理論

拎

• Analysis of Algorithms | Big-O analysis. GeeksForGeeks.