Što je Big-O notacija?

Što je Big-O notacija?

Jeste li se ikada zapitali zašto je programu koji ste napisali trebalo toliko dugo vremena da se pokrene? Možda biste htjeli znati možete li svoj kod učiniti učinkovitijim. Razumijevanje načina izvođenja koda može dovesti vaš kôd na sljedeću razinu. Big-O notacija zgodan je alat za izračunavanje koliko je vaš kôd zapravo učinkovit.





Što je Big-O notacija?

Big-O zapis daje vam način da izračunate koliko će vremena trebati za pokretanje vašeg koda. Možete fizički odrediti vrijeme potrebno za pokretanje koda, ali s tom metodom teško je uhvatiti male vremenske razlike. Na primjer, vrijeme potrebno za pokretanje 20 do 50 redaka koda vrlo je malo. Međutim, u velikom programu te se neučinkovitosti mogu zbrajati.



izvadite videozapis s web stranice

Big-O notacija broji koliko koraka algoritam mora izvršiti da bi ocijenio svoju učinkovitost. Pristup vašem kodu na ovaj način može biti vrlo učinkovit ako ga želite prilagoditi kako biste povećali učinkovitost. Oznaka Big-O omogućit će vam mjerenje različitih algoritama prema broju koraka koji su potrebni za izvođenje i objektivnu usporedbu učinkovitosti algoritama.





Kako izračunavate Big-O zapis?

Razmotrimo dvije funkcije koje broje koliko pojedinačnih čarapa ima u ladici. Svaka funkcija uzima broj parova čarapa i vraća broj pojedinačnih čarapa. Kôd je napisan na Pythonu, ali to ne utječe na to kako bismo računali broj koraka.

Algoritam 1:



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

Algoritam 2:

def sockCounter(numberOfPairs):
return numberOfPairs * 2

Ovo je glup primjer i trebali biste moći lako reći koji je algoritam učinkovitiji. No, radi vježbe, prođimo kroz svaku.



POVEZANE: Što je funkcija u programiranju?

Algoritam 1 ima mnogo koraka:



  1. Varijabli individualSocks dodjeljuje vrijednost nula.
  2. Varijabli i dodjeljuje vrijednost jedan.
  3. Uspoređuje vrijednost i s brojemOfParova.
  4. Dodaje dva u individualSocks.
  5. Povećanu vrijednost individualnih čarapa dodjeljuje sebi.
  6. Povećava i za jedan.
  7. Zatim se ponavlja kroz korake 3 do 6 isti broj puta kao (indiviualSocks - 1).

Broj koraka koje moramo dovršiti za algoritam jedan može se izraziti kao:

4n + 2

Četiri su koraka koja moramo dovršiti n puta. U ovom slučaju, n bi bilo jednako vrijednosti numberOfPairs. Postoje i 2 koraka koja se dovršavaju jednom.

Za usporedbu, algoritam 2 ima samo jedan korak. Vrijednost numberOfPairs množi se s dva. To bismo izrazili kao:

1

Ako to već nije bilo očito, sada možemo lako vidjeti da je algoritam 2 prilično učinkovitiji.

Big-O analiza

Općenito, kada ste zainteresirani za Big-O notaciju algoritma, više vas zanima ukupna učinkovitost, a manje za detaljnu analizu broja koraka. Da bismo pojednostavili zapis, možemo samo navesti veličinu učinkovitosti.

U gornjim primjerima, algoritam 2 bi se izrazio kao jedan:

O(1)

No algoritam 1 bio bi pojednostavljen na sljedeći način:

O(n)

Ovaj kratki snimak govori nam kako je učinkovitost algoritma jedna vezana za vrijednost n. Što je veći broj, više koraka će algoritam morati dovršiti.

Linearni kod

Kredit za sliku: Nick Fledderus/ Imenički projekt

Budući da ne znamo vrijednost n, korisnije je razmisliti o tome kako vrijednost n utječe na količinu koda koji se mora pokrenuti. U algoritmu 1 možemo reći da je odnos linearan. Ako iscrtate broj koraka u odnosu na vrijednost n, dobit ćete ravnu liniju koja se povećava.

Kvadratni kod

Nisu svi odnosi tako jednostavni kao linearni primjer. Zamislite da imate 2D niz i željeli biste tražiti vrijednost u nizu. Možete stvoriti ovakav algoritam:

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

U ovom primjeru, broj koraka ovisi o broju polja u arraySearched i broju vrijednosti u svakom nizu. Dakle, pojednostavljeni broj koraka bio bi n * n ili n².

web stranice za vrijeme kada vam je dosadno

Kredit za sliku: Nick Fledderus/ Imenički projekt

Taj je odnos kvadratni odnos, što znači da broj koraka u našem algoritmu raste eksponencijalno s n. U zapisu Big-O to biste napisali kao:

O(n²)

POVEZANE: Korisni alati za provjeru, čišćenje i optimizaciju CSS datoteka

Logaritamski kod

Iako postoje mnogi drugi odnosi, posljednji odnos koji ćemo pogledati su logaritamski odnosi. Za osvježavanje memorije zapisnik broja je eksponentna vrijednost potrebna za postizanje broja koji ima bazu. Na primjer:

log 2 (8) = 3

Dnevnik je jednak tri jer da nam je baza 2, potrebna nam je eksponentna vrijednost 3 da bismo došli do broja 8.

Kredit za sliku: Nick Fledderus/ Imenički projekt

Dakle, odnos logaritamske funkcije suprotan je eksponencijalnom odnosu. Kako se n povećava, za pokretanje algoritma potrebno je manje novih koraka.

Na prvi pogled to se čini kontra-intuitivno. Kako koraci algoritma mogu rasti sporije od n? Dobar primjer za to su binarna pretraživanja. Razmotrimo algoritam za traženje broja u nizu jedinstvenih vrijednosti.

  • Počet ćemo s nizom za pretraživanje koji je poredan od najmanjeg do najvećeg.
  • Zatim ćemo provjeriti vrijednost u sredini niza.
  • Ako je vaš broj veći, isključit ćemo niže brojeve u pretraživanju, a ako je broj bio manji, isključit ćemo veće brojeve.
  • Sada ćemo pogledati srednji broj preostalih brojeva.
  • Opet ćemo isključiti polovicu brojeva ovisno o tome je li naša ciljna vrijednost veća ili niža od srednje vrijednosti.
  • Nastavit ćemo ovaj proces dok ne pronađemo cilj ili utvrdimo da ga nema na popisu.

Kao što vidite, budući da binarna pretraživanja eliminiraju polovicu mogućih vrijednosti pri svakom prolazu, kako n postaje sve veći, učinak na broj provjeravanja niza jedva utječe. Da bismo to izrazili u zapisu Big-O, napisali bismo:

O(log(n))

Važnost Big-O notacije

Big-O nation daje vam brz i jednostavan način da ispričate koliko je algoritam učinkovit. To olakšava odabir između različitih algoritama. To može biti osobito korisno ako koristite algoritam iz knjižnice i ne znate nužno kako kôd izgleda.

windows 10 kako unijeti bios

Kad prvi put naučite kodirati, počinjete s linearnim funkcijama. Kao što možete vidjeti iz gornjeg grafikona, to će vas odvesti jako daleko. No, kako postajete iskusniji i počnete graditi složeniji kod, učinkovitost počinje postajati problem. Razumijevanje načina kvantificiranja učinkovitosti vašeg koda pružit će vam alate koji su vam potrebni za njegovo usklađivanje radi učinkovitosti i vaganje prednosti i nedostataka algoritama.

Udio Udio Cvrkut E -pošta 10 najčešćih grešaka u programiranju i kodiranju

Pogreške u kodiranju mogu dovesti do toliko problema. Ovi savjeti pomoći će vam da izbjegnete programske greške i zadržite svoj kôd smislenim.

Pročitajte Dalje Povezane teme
  • Programiranje
  • Programiranje
O autoru Jennifer Seaton(Objavljen 21 članak)

J. Seaton je znanstveni pisac specijaliziran za razbijanje složenih tema. Doktorirala je na Sveučilištu Saskatchewan; njezino se istraživanje usredotočilo na korištenje učenja zasnovanog na igrama za povećanje angažmana učenika na internetu. Kad ne radi, zateći ćete je kako čita, igra video igrice ili radi u vrtu.

Više od Jennifer Seaton

Pretplatite se na naše obavijesti

Pridružite se našem biltenu za tehničke savjete, recenzije, besplatne e -knjige i ekskluzivne ponude!

Kliknite ovdje za pretplatu