Big O Notation - Jednostavno objašnjeno ilustracijama i video zapisima

Velika O oznaka koristi se za priopćavanje brzine algoritma. To može biti važno kada procjenjujete algoritme drugih ljudi i kada procjenjujete svoje! U ovom ću članku objasniti što je oznaka Big O i dati vam popis najčešćih vremena izvođenja algoritama koji ga koriste.

Vrijeme izvođenja algoritma raste različitim brzinama

Moj sin Judah ima puno igračaka. Zapravo je stekao milijardu igračaka! Iznenadit ćete se koliko brzo dijete može dobiti toliko igračaka ako je prvo unuče s obje strane obitelji. ??

U svakom slučaju, Judah ima problem. Kada njegovi prijatelji posjete i žele se igrati s određenom igračkom, može potrajati zauvijek da je pronađe. Stoga želi stvoriti algoritam pretraživanja koji će mu pomoći da što brže pronađe određenu igračku. Pokušava odlučiti između dva različita algoritma pretraživanja: jednostavno pretraživanje i binarno pretraživanje. (Ne brinite ako niste upoznati s tim algoritmima.)

Odabrani algoritam mora biti brz i točan. S jedne strane, binarno pretraživanje je brže. A Judah ima samo otprilike 30 sekundi prije nego što njegovom prijatelju dosadi tražiti igračku. S druge strane, jednostavni algoritam pretraživanja lakše je napisati, a manja je šansa za uvođenje bugova. Sigurno bi bilo neugodno kad bi njegov prijatelj pronašao greške u njegovom kodu! Da bi bio posebno oprezan, Judah odluči oba algoritma vremenski prilagoditi popisom od 100 igračaka.

Pretpostavimo da je za provjeru jedne igračke potrebna 1 milisekunda. Jednostavnim pretraživanjem, Judah mora provjeriti 100 igračaka, pa potraga traje 100 ms. S druge strane, samo mora binarnim pretraživanjem provjeriti 7 igračaka (log2 100 je otprilike 7, ne brinite ako je ova matematika zbunjujuća jer nije glavna poanta ovog članka), tako da trajanje traje 7 ms trčati. Ali stvarno, popis će imati milijardu igračaka. Ako se dogodi, koliko će trajati jednostavno pretraživanje? Koliko će trajati binarno pretraživanje?

Vrijeme izvođenja jednostavnog pretraživanja u odnosu na binarno pretraživanje s popisom od 100 elemenata

Judah vodi binarno pretraživanje s milijardu igračaka i potrebno je 30 ms (log2 1,000,000,000 je otprilike 30). "32 ms!" misli. “Binarno pretraživanje je otprilike 15 puta brže od jednostavnog pretraživanja, jer je jednostavno trajanje trajalo 100 ms sa 100 elemenata, a binarno pretraživanje 7 ms. Dakle, za jednostavno pretraživanje potrebno je 30 × 15 = 450 ms, zar ne? Potpuno ispod 30 sekundi koliko je potrebno da se mom prijatelju dosadi. " Judah odluči krenuti s jednostavnom potragom. Je li to pravi izbor?

Ne. Ispada, Judah je pogriješio i doživotno je izgubio prijatelja. ? Vrijeme izvođenja jednostavnog pretraživanja s milijardu predmeta bit će milijardu ms, što je 11 dana! Problem je što vremena izvođenja binarnog pretraživanja i jednostavnog pretraživanja ne rastu istom brzinom.

Vrijeme izvođenja raste vrlo različitim brzinama! Kako se broj stavki povećava, binarnom pretraživanju treba malo više vremena, ali jednostavnom pretraživanju treba puno više vremena. Kako se popis brojeva povećava, binarno pretraživanje odjednom postaje puno brže od jednostavnog pretraživanja.

Dakle, Judah je pogriješio što je binarno pretraživanje uvijek 15 puta brže od jednostavnog pretraživanja. Ako postoji milijarda igračaka, to je više kao 33 milijuna puta brže.

Vrlo je važno znati kako se vrijeme rada povećava kako se veličina popisa povećava. Tu dolazi do oznake Big O.

Oznaka Big O govori vam koliko je algoritam brz. Na primjer, pretpostavimo da imate popis veličine n . Jednostavno pretraživanje treba provjeriti svaki element, tako da će biti potrebno n operacija. Vrijeme izvođenja u oznaci Big O je O ( n ).

Gdje su sekunde? Nema ih - Big O vam ne govori brzinu u sekundama. Oznaka Big O omogućuje vam usporedbu broja operacija. Govori vam kako brzo algoritam raste.

Učinimo još jedan primjer. Binarno pretraživanje treba log n operacije kako bi provjerilo popis veličine n . Koje je vrijeme prikazivanja u notaciji Big O? To je O (log n ). Općenito, oznaka Big O napisana je na sljedeći način.

To vam govori o broju operacija koje će algoritam izvršiti. Zove se Big O notation, jer ste ispred broja operacija stavili "veliko O".

Big O uspostavlja najgore vrijeme izvođenja

Pretpostavimo da pomoću jednostavnog pretraživanja tražite korisnika u svojoj bazi podataka. Znate da za jednostavno pretraživanje treba O ( n ) vremena, što znači da ćete u najgorem slučaju algoritam morati pregledati svakog korisnika u bazi podataka. U ovom slučaju tražite korisnika s imenom "aardvark213". Ovo je prvi korisnik na popisu. Dakle, vaš algoritam nije morao gledati svaki unos - pronašao ga je u prvom pokušaju. Je li algoritmu trebalo O ( n ) vremena? Ili je trebalo O (1) vremena jer je osobu pronašao u prvom pokušaju?

Jednostavno pretraživanje i dalje traje O ( n ) vrijeme. U ovom je slučaju algoritam odmah pronašao ono što je tražio. To je najbolji slučaj. No, oznaka Big O govori o najgorem scenariju. Dakle, možete reći da će u najgorem slučaju algoritam morati jednom pregledati svakog korisnika u bazi podataka. To je O ( n ) vrijeme. To je sigurnost - znate da jednostavno pretraživanje nikada neće biti sporije od O ( n ) vremena.

Neka uobičajena vremena pokretanja za Big O

Evo pet velikih vremena pokretanja s kojima ćete se često susresti, poredanih od najbržih do najsporijih:

  • O (log n ), poznato i kao vrijeme dnevnika. Primjer: binarno pretraživanje.
  • O ( n ), poznato i kao linearno vrijeme . Primjer: Jednostavno pretraživanje.
  • O ( n * log n ). Primjer: algoritam za brzo sortiranje, poput brzog sortiranja.
  • O ( n 2). Primjer: Polagani algoritam sortiranja, poput sortiranja odabira.
  • O ( n !). Primjer: Stvarno spor algoritam, poput putničkog prodavača.

Vizualizacija različitih Big O vremena izvođenja

Pretpostavimo da crtate mrežu od 16 okvira, a za to možete birati između 5 različitih algoritama. Ako koristite prvi algoritam, trebat će vam O (log n ) vrijeme za crtanje mreže. Možete napraviti 10 operacija u sekundi. S O (log n ) vremenom trebat će vam 4 operacije za crtanje mreže od 16 okvira (log 16 baza 2 je 4). Dakle, za crtanje mreže trebat će vam 0,4 sekunde. Što ako morate nacrtati 1024 kutije? Trebat će vam log 1024 = 10 operacija ili 1 sekunda da nacrtate mrežu od 1024 okvira. Ovi brojevi koriste prvi algoritam.

Drugi algoritam je sporiji: treba O ( n ) vremena. Za izvlačenje 16 kutija bit će potrebno 16 operacija, a za izvlačenje 1024 kutije trebat će 1.024 operacije. Koliko je to vremena u sekundama?

Evo koliko bi vremena trebalo za crtanje mreže za ostatak algoritama, od najbržeg do najsporijeg:

Postoje i druga vremena izvođenja, ali ovo je pet najčešćih.

Ovo je pojednostavljenje. U stvarnosti ne možete ovako uredno pretvoriti iz velikog vremena izvršavanja u brojne operacije, ali ovo je dobra procjena.

Zaključak

Evo glavnih za poneti:

  • Brzina algoritma ne mjeri se u sekundama, već u rastu broja operacija.
  • Umjesto toga, govorimo o tome kako se brzo vrijeme izvođenja algoritma povećava s povećanjem veličine ulaza.
  • Vrijeme izvođenja algoritama izražava se u zapisu Big O.
  • O (log n ) je brži od O ( n ), ali postaje puno brži kako popis stavki koje pretražujete raste.

A evo i videozapisa koji pokriva mnogo toga u ovom članku i više.

Nadam se da vam je ovaj članak donio više jasnosti u vezi s oznakom Big O. Ovaj se članak temelji na lekciji iz mog video tečaja iz Manning Publications pod nazivom Algoritmi u pokretu. Tečaj se temelji na nevjerojatnoj knjizi Grokking Algorithms Adita Bhargave. On je taj koji je nacrtao sve zabavne ilustracije u ovom članku.

Ako najbolje učite kroz knjige, nabavite knjigu! Ako najbolje učite putem videozapisa, razmislite o kupnji mog tečaja. Pomoću koda ' 39carnes ' možete dobiti moj popust od 39% .