大 O 符號
大 O 符號(粵拼:daai6 ou1 fu4 hou2;英文:big O notation)係演算法分析上成日用嘅一種符號,攞嚟表示一隻演算法嘅運算複雜度[1]:1.1.3。
概論
好多資訊科技嘅工作,都涉及分析手上嘅演算法「有幾複雜」,例如家陣有班電腦科學家想提出一隻新嘅演算法,佢哋可以做嘅,就係攞隻新演算法去解問題,跟住又攞舊有嗰啲演算法解,畀人睇到「隻新演算法嘅複雜度低過打前嗰啲演算法,但解問題嗰陣嘅效用依然係咁好」[2][3]。喺實際應用上,佢哋通常會將運算複雜度表達做 input 嘅大細嘅函數,即係[1]:1.1.3
「 | 」 |
大 O 符號嘅做法就係建基於上面條原則嘅。喺大 O 符號之下,一隻演算法嘅時間複雜度同空間複雜度通常寫成類似噉嘅樣:
當中 係個 input 嘅大細(例如如果個輸入係個數字, 會係佢有幾多個位), 反映隻演算法要行嘅步嘅數量隨 嘅變化,例如:
- 當 係 10,隻演算法頂攏要行 10 步,或者頂攏要行 10 咁多步( 係個正嘅常數);
- 當 係 10,000,隻演算法頂攏要行 40,000 步,或者頂攏要行 40,000 咁多步;
... 如此類推。數學化啲噉講,如果話 ,意思即係有個正整數 同正常數 ,並且
假設每一步消耗嘅時間都一樣係 咁長,噉隻演算法行起上嚟要消耗嘅時間(時間複雜度)就可以輕易計到出嚟。
算法分類
- -隻演算法無論 係幾多,最大複雜度都唔變;
- -隻演算法嘅複雜度同 成線性關係,例如線性搜尋(linear search)就係噉;
- -隻演算法嘅複雜度同 成線性關係,例如對分搜尋(binary search)就係噉;
... 呀噉。上述呢啲「唔同款嘅複雜度」可以用下圖噉嘅方式想像:設 做「要行嘅步嘅數量」,下圖裏面嘅 Y 軸係 而 X 軸就係 ;隨住 數值升 會跟住升,而「唔同款嘅複雜度」就可以想像成「唔同形狀嘅線」-
細 o 符號
細 o 符號(little o):「 係 」(「 係 嘅細 O」)意思係指 增長得快過 好多。
大 omega 符號
註釋
睇埋
攷
拎
- Analysis of Algorithms | Big-O analysis. GeeksForGeeks.