Veliki O zapis objašnjen primjerima

Oznaka Big O način je za opisivanje brzine ili složenosti datog algoritma. Ako vaš trenutni projekt zahtijeva unaprijed definirani algoritam, važno je razumjeti koliko je brz ili spor u usporedbi s drugim opcijama.

Što je oznaka Big O i kako to funkcionira?

Jednostavno rečeno, oznaka Big O govori vam broj operacija koje će algoritam izvršiti. Ime dobiva iz doslovnog "Velikog O" ispred procijenjenog broja operacija.

Ono što vam notacija Big O ne govori je brzina algoritma u sekundama. Previše je čimbenika koji utječu na vrijeme rada algoritma. Umjesto toga, upotrijebit ćete oznaku Big O za usporedbu različitih algoritama prema broju operacija koje izvrše.

Big O uspostavlja najgore vrijeme izvođenja

Zamislite da ste učiteljica s učenicom Jane. Želite pronaći njezine zapise, pa koristite jednostavni algoritam pretraživanja da biste pregledali bazu podataka vašeg školskog okruga.

Znate da za jednostavno pretraživanje treba O (n) puta. To znači da ćete u najgorem slučaju morati pretražiti svaki pojedini zapis (predstavljen s n) kako biste pronašli Janein.

Ali kada pokrenete jednostavno pretraživanje, ustanovit ćete da su Janeini zapisi prvi unos u bazu podataka. Ne morate gledati svaki unos - pronašli ste ga u prvom pokušaju.

Je li ovom algoritmu trebalo O (n) vremena? Ili je trebalo O (1) vremena jer ste pronašli Janeine zapise u prvom pokušaju?

U ovom je slučaju 0 (1) najbolji slučaj - imali ste sreće da su Janeini zapisi bili na vrhu. No, oznaka Big O usredotočena je na najgori mogući scenarij, a to je 0 (n) za jednostavno pretraživanje. Osiguranje je da jednostavno pretraživanje nikada neće biti sporije od O (n) vremena.

Vrijeme izvođenja algoritma raste različitim brzinama

Pretpostavimo da je za provjeru svakog elementa u bazi podataka školskog okruga potrebna 1 milisekunda.

Jednostavnim pretraživanjem, ako morate provjeriti 10 unosa, trčanje će trebati 10 ms. Ali s algoritmom binarnog pretraživanja , morate provjeriti samo 3 elementa, za što je potrebno 3 ms.

U većini slučajeva popis ili baza podataka koju trebate pretraživati ​​sadržavat će stotine ili tisuće elemenata.

Ako postoji 1 milijarda elemenata, korištenje jednostavnog pretraživanja trajat će do milijardu ms ili 11 dana. S druge strane, korištenje binarnog pretraživanja potrajat će samo 32 ms u najgorem slučaju:

Jasno je da vrijeme izvođenja jednostavnog pretraživanja i binarnog pretraživanja ne raste gotovo jednakom brzinom. Kako se popis unosa povećava, binarnom pretraživanju treba samo malo više vremena. Vrijeme izvođenja jednostavnog pretraživanja eksponencijalno raste kako se povećava popis unosa.

Zbog toga je toliko važno znati kako se vrijeme izvođenja povećava u odnosu na veličinu popisa. I upravo je tu oznaka Big O tako korisna.

Velika O oznaka prikazuje broj operacija

Kao što je gore spomenuto, oznaka Big O ne pokazuje vrijeme kada će algoritam raditi. Umjesto toga, prikazuje broj operacija koje će izvršiti. Govori vam kako brzo algoritam raste i omogućuje vam usporedbu s drugima.

Evo nekoliko uobičajenih algoritama i vremena njihovog izvođenja u notaciji Big O:

Veliki O zapisPrimjer algoritma
O (zapisnik n)Binarna pretraga
Na)Jednostavno pretraživanje
O (n * log n)Quicksort
O (n2)Sortiranje odabira
Na!)Putnički prodavač

Sada znate dovoljno da budete opasni s oznakom Big O. Izađite tamo i počnite uspoređivati ​​algoritme.