From Wikipedia, the free encyclopedia
大 O 符號(粵拼:daai6 ou1 fu4 hou2;英文:big O notation)係演算法分析上成日用嘅一種符號,攞嚟表示一隻演算法嘅運算複雜度[1]:1.1.3。
呢篇文 需要熟悉呢方面嘅人幫手寫。 |
好多資訊科技嘅工作,都涉及分析手上嘅演算法「有幾複雜」,例如家陣有班電腦科學家想提出一隻新嘅演算法,佢哋可以做嘅,就係攞隻新演算法去解問題,跟住又攞舊有嗰啲演算法解,畀人睇到「隻新演算法嘅複雜度低過打前嗰啲演算法,但解問題嗰陣嘅效用依然係咁好」[2][3]。喺實際應用上,佢哋通常會將運算複雜度表達做 input 嘅大細嘅函數,即係[1]:1.1.3
「 | 」 |
大 O 符號嘅做法就係建基於上面條原則嘅。喺大 O 符號之下,一隻演算法嘅時間複雜度同空間複雜度通常寫成類似噉嘅樣:
當中 係個 input 嘅大細(例如如果個輸入係個數字, 會係佢有幾多個位), 反映隻演算法要行嘅步嘅數量隨 嘅變化,例如:
... 如此類推。數學化啲噉講,如果話 ,意思即係有個正整數 同正常數 ,並且
假設每一步消耗嘅時間都一樣係 咁長,噉隻演算法行起上嚟要消耗嘅時間(時間複雜度)就可以輕易計到出嚟。
... 呀噉。上述呢啲「唔同款嘅複雜度」可以用下圖噉嘅方式想像:設 做「要行嘅步嘅數量」,下圖裏面嘅 Y 軸係 而 X 軸就係 ;隨住 數值升 會跟住升,而「唔同款嘅複雜度」就可以想像成「唔同形狀嘅線」-
細 o 符號(little o):「 係 」(「 係 嘅細 O」)意思係指 增長得快過 好多。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.