Ano ang Big-O Notation?

Ano ang Big-O Notation?

Naisip mo ba kung bakit ang isang programa na iyong sinulat ay napakatagal upang mapatakbo? Marahil ay nais mong malaman kung maaari mong gawing mas mahusay ang iyong code. Ang pag-unawa sa kung paano tatakbo ang code ay maaaring magdala ng iyong code sa susunod na antas. Ang Big-O notation ay isang madaling gamiting tool upang makalkula kung gaano kahusay ang iyong code.





Ano ang Big-O Notation?

Binibigyan ka ng Big-O notation ng isang paraan upang makalkula kung gaano katagal aabutin ang iyong code. Maaari mong pisikal na oras kung gaano katagal tumakbo ang iyong code, ngunit sa pamamaraang iyon, mahirap makibalita ng kaunting pagkakaiba sa oras. Halimbawa, ang oras na tumatagal sa pagitan ng pagpapatakbo ng 20 at 50 mga linya ng code ay napakaliit. Gayunpaman, sa isang malaking programa, ang mga kahusayan na iyon ay maaaring magdagdag.



kung paano tanggalin ang isang pahina ng break sa salita

Binibilang ng notasyon ng Big-O kung gaano karaming mga hakbang ang dapat isagawa ng isang algorithm upang masukat ang kahusayan nito. Ang paglapit sa iyong code sa ganitong paraan ay maaaring maging napaka epektibo kung kailangan mong ibagay ang iyong code upang madagdagan ang kahusayan. Ang notasyong Big-O ay magbibigay-daan sa iyo upang sukatin ang iba't ibang mga algorithm sa bilang ng mga hakbang na kinakailangan nito upang tumakbo at objectively na ihambing ang kahusayan ng mga algorithm.





Paano Mo Nakakalkula ang Big-O Notation

Isaalang-alang natin ang dalawang pagpapaandar na bilangin kung gaano karaming mga indibidwal na medyas ang nasa isang drawer. Ang bawat pag-andar ay tumatagal ng bilang ng mga pares ng medyas at ibabalik ang bilang ng mga indibidwal na medyas. Ang code ay nakasulat sa Python, ngunit hindi ito nakakaapekto kung paano namin bibilangin ang bilang ng mga hakbang.

Algorithm 1:



def sockCounter(numberOfPairs):
individualSocks = 0
for x in range(numberOfPairs):
individualSocks = individualSocks + 2
return individualSocks

Algorithm 2:

def sockCounter(numberOfPairs):
return numberOfPairs * 2

Ito ay isang hangal na halimbawa, at dapat mong madaling sabihin kung aling algorithm ang mas mahusay. Ngunit para sa pagsasanay, patakbuhin natin ang bawat isa.



KAUGNAYAN: Ano ang isang Pag-andar sa Programming?

Ang algorithm 1 ay may maraming mga hakbang:



  1. Nagtatalaga ito ng isang halaga ng zero sa variable na individualSocks.
  2. Nagtatalaga ito ng isang halaga ng isa sa variable i.
  3. Inihahambing nito ang halaga ng i sa numberOfPairs.
  4. Nagdaragdag ito ng dalawa sa mga indibidwal naSock.
  5. Itinalaga nito ang nadagdagang halaga ng mga indibidwal naSock sa sarili nito.
  6. Nagdaragdag ito ng isa.
  7. Pagkatapos ay maiikot ito pabalik sa pamamagitan ng mga hakbang 3 hanggang 6 para sa parehong bilang ng mga beses tulad ng (indiviualSocks - 1).

Ang bilang ng mga hakbang na mayroon kami upang makumpleto para sa isang algorithm ay maaaring ipahayag bilang:

4n + 2

Mayroong apat na mga hakbang na mayroon kami upang makumpleto n beses. Sa kasong ito, n ay katumbas ng halaga ng numberOfPairs. Mayroon ding 2 mga hakbang na nakumpleto nang isang beses.

Sa paghahambing, ang algorithm 2 ay may isang hakbang lamang. Ang halaga ng numberOfPair ay pinarami ng dalawa. Ipapahayag namin iyon bilang:

1

Kung hindi pa ito maliwanag, madali na nating makita na ang algorithm 2 ay mas mabisa nang kaunti.

Big-O Pagsusuri

Pangkalahatan, kapag interesado ka sa notasyong Big-O ng isang algorithm, mas interesado ka sa pangkalahatang kahusayan at mas kaunti sa pag-aaral ng pinong butil ng bilang ng mga hakbang. Upang gawing simple ang notasyon, maaari lamang nating sabihin ang laki ng kahusayan.

Sa mga halimbawa sa itaas, ang algorithm 2 ay ipahayag bilang isa:

O(1)

Ngunit ang algorithm 1 ay mapapadali bilang:

O(n)

Sinasabi sa amin ng mabilis na snapshot na ito kung paano ang kahusayan ng isang algorithm ay nakatali sa halaga ng n. Ang mas malaki ang bilang ng mas maraming mga hakbang na kakailanganin ng algorithm upang makumpleto.

Linear Code

Credit sa Larawan: Nick Fledderus / Proyekto ng Pangngalan

Dahil hindi namin alam ang halaga ng n, mas kapaki-pakinabang na isipin kung paano nakakaapekto ang halaga ng n sa dami ng code na kailangang tumakbo. Sa algorithm 1 maaari nating sabihin na ang relasyon ay linear. Kung balangkas mo ang bilang ng mga hakbang kumpara sa halaga ng n makakakuha ka ng isang tuwid na linya na pataas.

Quadratic Code

Hindi lahat ng mga relasyon ay kasing simple ng linear na halimbawa. Isipin na mayroon kang isang 2D array at nais mong maghanap para sa isang halaga sa array. Maaari kang lumikha ng isang algorithm tulad nito:

def searchForValue(targetValue, arraySearched):
foundTarget = False
for x in arraySearched:
for y in x:
if(y == targetValue):
foundTarget = True
return foundTarget

Sa halimbawang ito, ang bilang ng mga hakbang ay nakasalalay sa bilang ng mga arrays sa arraySearched at ang bilang ng mga halaga sa bawat array. Kaya, ang pinasimple na bilang ng mga hakbang ay n * n o n².

hindi nagpapakita ng panlabas na hard drive sa aking computer

Credit sa Larawan: Nick Fledderus / Proyekto ng Pangngalan

Ang ugnayan na ito ay isang quadratic na ugnayan, na nangangahulugang ang bilang ng mga hakbang sa aming algorithm ay lumalaki nang exponentially sa n. Sa Big-O notasyon, isusulat mo ito bilang:

O(n²)

KAUGNAYAN: Mga kapaki-pakinabang na tool upang Suriin, Linisin, at I-optimize ang Mga CSS File

Logarithmic Code

Bagaman maraming iba pang mga relasyon, ang huling relasyon na titingnan namin ay mga relasyon sa logaritmiko. Upang i-refresh ang iyong memorya, ang log ng isang numero ay ang exponent na halaga na kinakailangan upang maabot ang isang numero na binigyan ng isang base. Halimbawa:

log 2 (8) = 3

Ang log ay katumbas ng tatlo dahil kung ang aming base ay 2, kakailanganin namin ang isang exponent na halaga ng 3 upang makarating sa numero 8.

Credit sa Larawan: Nick Fledderus / Proyekto ng Pangngalan

Kaya, ang ugnayan ng isang function na logarithmic ay kabaligtaran ng isang exponential na relasyon. Habang tumataas, mas kaunting mga bagong hakbang ang kinakailangan upang patakbuhin ang algorithm.

Sa isang unang tingin, ito ay tila kontra-intuitive. Paano magiging mas mabagal ang mga hakbang ng isang algorithm kaysa sa n? Ang isang magandang halimbawa nito ay ang mga paghahanap sa binary. Isaalang-alang natin ang isang algorithm upang maghanap para sa isang numero sa isang hanay ng mga natatanging halaga.

  • Magsisimula kami sa isang array upang maghanap na ayon sa pinakamaliit hanggang sa pinakamalaki.
  • Susunod, susuriin namin ang halaga sa gitna ng array.
  • Kung mas mataas ang iyong numero, ibubukod namin ang mga mas mababang numero sa aming paghahanap at kung ang numero ay mas mababa, ibubukod namin ang mas mataas na mga numero.
  • Ngayon, titingnan natin ang gitnang numero ng mga natitirang numero.
  • Muli, ibubukod namin ang kalahati ng mga numero batay sa kung ang aming target na halaga ay mas mataas o mas mababa kaysa sa gitnang halaga.
  • Ipagpatuloy namin ang prosesong ito hanggang sa makita namin ang aming target, o matukoy na wala ito sa listahan.

Tulad ng nakikita mo, dahil ang mga paghahanap sa binary ay tinanggal ang kalahati ng mga posibleng halaga sa bawat pass, habang lumalaki ang n, ang epekto sa bilang ng beses na suriin natin ang array ay bahagyang naapektuhan. Upang ipahayag ito sa Big-O notation, magsusulat kami:

O(log(n))

Ang Kahalagahan ng Big-O Notation

Big-O bansa ay nagbibigay sa iyo ng isang mabilis at madaling paraan upang makipag-usap kung gaano kahusay ang isang algorithm. Ginagawa nitong mas madali upang magpasya sa pagitan ng iba't ibang mga algorithm. Maaari itong maging partikular na kapaki-pakinabang kung gumagamit ka ng isang algorithm mula sa isang silid-aklatan at hindi kinakailangang malaman kung ano ang hitsura ng code.

maglipat ng mga file sa android mula sa mac

Kapag natutunan mo munang mag-code, nagsisimula ka sa mga linear function. Tulad ng nakikita mo mula sa grap sa itaas, makakapagpalayo kana sa iyo. Ngunit habang ikaw ay naging mas may karanasan at nagsimulang bumuo ng mas kumplikadong code, ang kahusayan ay nagsisimulang maging isang problema. Ang isang pag-unawa sa kung paano sukatin ang kahusayan ng iyong code ay magbibigay sa iyo ng mga tool na kailangan mo upang simulan ang pag-tune nito para sa kahusayan at pagtimbang ng mga kalamangan at kahinaan ng mga algorithm.

Magbahagi Magbahagi Mag-tweet Email 10 Karamihan sa Karaniwang Mga Pagkakamali sa Programming at Coding

Ang pag-coding ng mga pagkakamali ay maaaring humantong sa napakaraming mga problema. Tutulungan ka ng mga tip na ito na maiwasan ang mga pagkakamali sa pagprograma at panatilihing makabuluhan ang iyong code.

Basahin Susunod Mga Kaugnay na Paksa
  • Programming
  • Programming
Tungkol sa May-akda Jennifer Seaton(21 Artikulo Nai-publish)

Si J. Seaton ay isang manunulat ng Agham na dalubhasa sa pagwawasak ng mga kumplikadong paksa. Mayroon siyang PhD mula sa University of Saskatchewan; ang kanyang pananaliksik ay nakatuon sa paggamit ng pag-aaral na batay sa laro upang madagdagan ang pakikipag-ugnayan ng mag-aaral sa online. Kapag hindi siya nagtatrabaho, mahahanap mo siya sa kanyang pagbabasa, paglalaro ng mga video game, o paghahardin.

Higit pa Mula kay Jennifer Seaton

Mag-subscribe sa aming newsletter

Sumali sa aming newsletter para sa mga tip sa tech, pagsusuri, libreng ebook, at eksklusibong deal!

Mag-click dito upang mag-subscribe