Što je Big-O notacija?

Jeste li se ikad zapitali zašto je programu koji ste napisali trebalo toliko dugo da se pokrene? Možda biste htjeli znati možete li svoj kod učiniti učinkovitijim. Razumijevanje kako se kôd izvodi može vaš kôd dovesti na sljedeću razinu. Oznaka Big-O praktičan je alat za izračunavanje učinkovitosti vašeg koda.

Što je oznaka Big-O?

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

Oznaka Big-O broji koliko koraka algoritam mora izvršiti da bi se procijenila njegova učinkovitost. Pristup vašem kodu na ovaj način može biti vrlo učinkovit ako trebate prilagoditi svoj kôd kako biste povećali učinkovitost. Oznaka Big-O omogućit će vam mjerenje različitih algoritama brojem koraka potrebnih za pokretanje i objektivnu usporedbu učinkovitosti algoritama.

Kako izračunavate Big-O notaciju

Razmotrimo dvije funkcije koje broje koliko je pojedinačnih čarapa 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
za x u rasponu (numberOfPairs):
individualSocks = individualSocks + 2
vratite individualSocks

Algoritam 2:

def sockCounter (numberOfPairs):
povratni brojPairs * 2

Ovo je glup primjer i trebali biste lako znati koji je algoritam učinkovitiji. Ali za vježbu, prođimo kroz svaku.

POVEZANO: Što je funkcija u programiranju?

Što je funkcija u programiranju?

Ako učite kako programirati vlastiti kod, morat ćete razumjeti koje su funkcije.

Algoritam 1 ima mnogo koraka:

1. Varijabli individualSocks dodjeljuje vrijednost nula.
2. Varijabli i dodjeljuje vrijednost jedan.
3. Uspoređuje vrijednost i s numberOfPairs.
4. Dodaje dva na individualSocks.
5. Povećava vrijednost individualSocks dodjeljuje sebi.
6. Povećava se za jedan.
7. Zatim se petljama vraća kroz korake 3 do 6 isti broj puta kao i (indiviualSocks - 1).

Broj koraka koje moramo obaviti za jedan algoritam može se izraziti kao:

4n + 2

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

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

1

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

Big-O analiza

Općenito, kada vas zanima Big-O oznaka algoritma, više vas zanima ukupna učinkovitost, a manje analiza sitnih zrna broja koraka. Da bismo pojednostavili zapis, možemo samo navesti veličinu učinkovitosti.

U gornjim primjerima algoritam 2 izrazio bi se kao jedan:

O (1)

Ali algoritam 1 bio bi pojednostavljen kao:

Na)

Ova kratka snimka govori nam kako je učinkovitost algoritma jedan povezana s vrijednošću n. Što je veći broj, algoritam će trebati izvršiti više koraka.

Linearni kod

Budući da ne znamo vrijednost n, korisnije je razmisliti o tome kako vrijednost n utječe na količinu koda koji treba pokrenuti. U algoritmu 1 možemo reći da je veza linearna. Ako ucrtate broj koraka vs. vrijednost n dobivate ravnu crtu koja ide prema gore.

Kvadratni kod

Nisu svi odnosi tako jednostavni kao linearni primjer. Zamislite da imate 2D niz i želite potražiti vrijednost u nizu. Možete stvoriti algoritam poput ovog:

def searchForValue (targetValue, arraySearched):
foundTarget = Netačno
za x u nizuPretraženo:
za y u x:
if (y == targetValue):
foundTarget = Tačno
povratak foundTarget

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

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

O (n²)

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

Logaritamski kod

Iako postoji mnogo drugih odnosa, posljednji odnos koji ćemo razmotriti je logaritamski odnos. Da biste osvježili svoju memoriju, zapisnik broja je vrijednost eksponenta potrebna za dostizanje broja kojem je dana baza. Na primjer:

log 2 (8) = 3

Zapisnik je jednak tri, jer da je naša baza 2, trebamo eksponentnu vrijednost 3 da bismo došli do broja 8.

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

Na prvi pogled ovo se čini kontra-intuitivnim. 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.

• Započet ćemo s nizom za pretraživanje po redoslijedu od najmanjeg do najvećeg.
• Dalje, provjerit ćemo vrijednost u sredini polja.
• Ako je vaš broj veći, izuzeti ćemo niže brojeve u našoj pretrazi, a ako je taj broj bio manji, izuzeti ćemo veće brojeve.
• Sada ćemo pogledati srednji broj preostalih brojeva.
• Opet ćemo izuzeti polovinu brojeva na temelju toga je li naša ciljana vrijednost viša ili niža od srednje vrijednosti.
• Nastavit ćemo ovaj postupak dok ne pronađemo svoju metu ili utvrdimo da je nema na popisu.

Kao što vidite, budući da binarna pretraživanja eliminiraju polovicu mogućih vrijednosti pri svakom prolazu, jer n postaje veći, učinak na broj provjera niza gotovo nije pogođen. Da bismo to izrazili u Big-O notaciji, napisali bismo:

O (log (n))

Važnost notacije Big-O

Big-O nation pruža vam brz i jednostavan način da komunicirate koliko je algoritam učinkovit. To olakšava odlučivanje između različitih algoritama. To može biti posebno korisno ako koristite algoritam iz knjižnice i ne morate nužno znati kako kôd izgleda.

Kada prvi put naučite kodirati, započinjete s linearnim funkcijama. Kao što vidite iz gornjeg grafikona, to će vas odvesti jako daleko. No kako postajete iskusniji i počinjete graditi složeniji kod, učinkovitost počinje postajati problem. Razumijevanje načina kvantificiranja učinkovitosti koda pružit će vam alate potrebne za početak podešavanja učinkovitosti i vaganje prednosti i nedostataka algoritama.

10 najčešćih pogrešaka u programiranju i kodiranju

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

O autoru