Notarea Big O este o modalitate de a descrie viteza sau complexitatea unui algoritm dat. Dacă proiectul dvs. actual necesită un algoritm predefinit, este important să înțelegeți cât de rapid sau de lent este comparat cu alte opțiuni.

Ce este notația Big O și cum funcționează?

Nota O mare explicata cu

Mai simplu spus, notația Big O vă spune numărul de operații pe care le va face un algoritm. Își primește numele de la literalul „Big O” din fața numărului estimat de operații.

Ceea ce notația Big O nu vă spune este viteza algoritmului în câteva secunde. Există mult prea mulți factori care influențează timpul necesar unui algoritm pentru a rula. În schimb, veți folosi notația Big O pentru a compara diferiți algoritmi în funcție de numărul de operații pe care le fac.

Big O stabilește un timp de rulare în cel mai rău caz

Imaginați-vă că sunteți un profesor cu o elevă pe nume Jane. Vrei să îi găsești înregistrările, așa că folosești un algoritm simplu de căutare pentru a trece prin baza de date a districtului tău școlar.

Știți că o căutare simplă durează O (n) ori pentru a rula. Acest lucru înseamnă că, în cel mai rău caz, va trebui să căutați fiecare înregistrare (reprezentată de n) pentru a găsi Jane.

Dar când executați căutarea simplă, constatați că înregistrările lui Jane sunt prima intrare în baza de date. Nu trebuie să te uiți la fiecare intrare – ai găsit-o la prima încercare.

A luat acest algoritm O (n) timp? Sau a durat O (1) timp pentru că ați găsit înregistrările lui Jane la prima încercare?

În acest caz, 0 (1) este cel mai bun scenariu – ai avut norocul că înregistrările lui Jane s-au situat la vârf. Notarea Big O se concentrează însă pe cel mai rău caz, care este 0 (n) pentru căutare simplă. Este o asigurare că căutarea simplă nu va fi niciodată mai lentă decât O (n) timp.

Timpul de funcționare al algoritmului crește la rate diferite

Să presupunem că este nevoie de 1 milisecundă pentru a verifica fiecare element din baza de date a districtului școlar.

Cu o căutare simplă, dacă trebuie să verificați 10 intrări, va dura 10 ms pentru a rula. Dar cu algoritm de căutare binară, trebuie doar să verificați 3 elemente, care durează 3 ms pentru a rula.

În majoritatea cazurilor, lista sau baza de date pe care trebuie să o căutați va avea sute sau mii de elemente.

Dacă există 1 miliard de elemente, utilizarea căutării simple va dura până la 1 miliard ms, sau 11 zile. Pe de altă parte, utilizarea căutării binare va dura doar 32 ms în cel mai rău caz:

1611737644 191 Nota O mare explicata cu

În mod clar, timpul de funcționare pentru căutare simplă și căutare binară nu crește aproape la același ritm. Pe măsură ce lista de intrări devine mai mare, căutarea binară necesită doar puțin mai mult timp pentru a rula. Durata de rulare a căutării simple crește exponențial pe măsură ce lista de intrări crește.

Acesta este motivul pentru care cunoașterea timpului de funcționare crește în raport cu dimensiunea listei este atât de importantă. Și tocmai aici notația Big O este atât de utilă.

Notația O mare arată numărul de operații

După cum sa menționat mai sus, notația Big O nu arată timp va rula un algoritm. În schimb, arată numărul de operații pe care le va efectua. Vă spune cât de repede crește un algoritm și vă permite să îl comparați cu alții.

1611737644 936 Nota O mare explicata cu

Iată câțiva algoritmi obișnuiți și timpul lor de rulare în notația Big O:

Notare O mareExemplu de algoritm
O (jurnal n)Căutare binară
Pe)Căutare simplă
O (n * jurnal n)Sortare rapida
O (n2)Sortare selecție
Pe!)Vânzător de călătorii

Acum știți suficient pentru a fi periculos cu notația Big O. Ieșiți acolo și începeți să comparați algoritmi.