Notare O mare explicata simplu cu ilustratii si videoclipuri
Ilustrație (și cele mai multe din acest articol) de Adit Bhargava

Notația O mare este utilizată pentru a comunica cât de rapid este un algoritm. Acest lucru poate fi important atunci când evaluați algoritmii altor persoane și când evaluați propriul dvs.! În acest articol, voi explica ce este notația Big O și vă voi oferi o listă cu cele mai frecvente perioade de rulare pentru algoritmi care o utilizează.

Timpii de funcționare ai algoritmului cresc la rate diferite

Notare O mare explicata simplu cu ilustratii si videoclipuri
Fiul meu explică notația mare „O”.

Fiul meu Judah are o mulțime de jucării. De fapt, el a dobândit un miliard jucarii! Ai fi surprins cât de repede un copil poate obține atâtea jucării dacă el este primul nepot de ambele părți ale familiei. ??

Oricum, Iuda are o problemă. Când prietenii săi vizitează și doresc să se joace cu o jucărie specifică, poate dura TOTUL pentru a găsi jucăria. Așa că vrea să creeze un algoritm de căutare care să-l ajute să găsească o jucărie specifică cât mai rapid posibil. El încearcă să decidă între doi algoritmi de căutare diferiți: căutare simplă și căutare binară. (Nu vă faceți griji dacă nu sunteți familiarizați cu acești algoritmi.)

Algoritmul ales trebuie să fie rapid și corect. Pe de o parte, căutarea binară este mai rapidă. Iar Iuda are adesea doar aproximativ 30 secunde înainte ca prietenul său să se plictisească în căutarea unei jucării. Pe de altă parte, un algoritm de căutare simplu este mai ușor de scris și există mai puține șanse de a fi introduse erori. Sigur ar fi jenant dacă prietenul său va găsi bug-uri în codul său! Pentru a fi foarte atent, Judah decide să programeze ambii algoritmi cu o listă de 100 de jucării.

Să presupunem că este nevoie de 1 milisecundă pentru a verifica o jucărie. Cu o căutare simplă, Judah trebuie să verifice 100 de jucării, astfel încât căutarea durează 100 ms pentru a rula. Pe de altă parte, trebuie doar să verifice 7 jucării cu căutare binară (log2 100 este aproximativ 7, nu vă faceți griji dacă această matematică este confuză, deoarece nu este punctul principal al acestui articol), astfel încât căutarea durează 7 ms a alerga. Dar, într-adevăr, lista va avea un miliard de jucării. În caz contrar, cât va dura o căutare simplă? Cât va dura căutarea binară?

1611645011 570 Notare O mare explicata simplu cu ilustratii si videoclipuri

Timp de rulare pentru căutare simplă vs. căutare binară, cu o listă de 100 de elemente

Judah efectuează căutări binare cu 1 miliard de jucării și durează 30 ms (log2 1.000.000.000 este aproximativ 30). „32 ms!” el crede. „Căutarea binară este de aproximativ 15 ori mai rapidă decât cea simplă, deoarece căutarea simplă a durat 100 ms cu 100 de elemente, iar căutarea binară a durat 7 ms. Deci, căutarea simplă va dura 30 × 15 = 450 ms, nu? Sub 30 de secunde este nevoie ca prietenul meu să se plictisească ”. Iuda decide să meargă cu o căutare simplă. Aceasta este alegerea corectă?

Nu. Se pare că Iuda a greșit și și-a pierdut un prieten pe viață. ? Durata de rulare pentru căutarea simplă cu 1 miliard de articole va fi de 1 miliard ms, adică 11 zile! Problema este, timpii de rulare pentru căutare binară și căutare simplă dnu crește în același ritm.

1611645012 159 Notare O mare explicata simplu cu ilustratii si videoclipuri

Timpii de rulare cresc la viteze foarte diferite! Pe măsură ce numărul de articole crește, căutarea binară durează puțin mai mult pentru a rula, dar căutarea simplă necesită o lot mai mult timp pentru a alerga. Deci, pe măsură ce lista numerelor devine mai mare, căutarea binară devine brusc un lot mai rapid decât simpla căutare.

Deci, Iuda s-a înșelat cu privire la căutarea binară fiind întotdeauna de 15 ori mai rapidă decât simpla căutare. Dacă există 1 miliard de jucării, este mai mult de 33 de milioane de ori mai rapid.

Este foarte important să știți cum crește timpul de funcționare pe măsură ce crește dimensiunea listei. Aici intervine notația Big O.

Notarea Big O vă spune cât de rapid este un algoritm. De exemplu, să presupunem că aveți o listă de dimensiuni n. Căutarea simplă trebuie să verifice fiecare element, așa că va dura n operațiuni. Durata de rulare în notația Big O este O (n).

Unde sunt secundele? Nu există – Big O nu vă spune viteza în câteva secunde. Notarea Big O vă permite să comparați numărul de operații. Vă spune cât de repede crește algoritmul.

Să facem un alt exemplu. Căutarea binară are nevoie de jurnal n operații pentru a verifica o listă de dimensiuni n. Care este timpul de funcționare în notația Big O? Este O (log n). În general, notația Big O este scrisă după cum urmează.

1611645012 206 Notare O mare explicata simplu cu ilustratii si videoclipuri

Aceasta vă arată numărul de operații pe care le va face un algoritm. Se numește notație Big O, deoarece puneți un „O mare” în fața numărului de operații.

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

Notare O mare explicata simplu cu ilustratii si videoclipuri

Să presupunem că utilizați căutarea simplă pentru a căuta un utilizator în baza de date a utilizatorilor. Știi că căutarea simplă necesită O (n) timpul de rulare, ceea ce înseamnă că, în cel mai rău caz, algoritmul va trebui să caute prin fiecare utilizator din baza de date. În acest caz, căutați un utilizator cu numele „aardvark213”. Acesta este primul utilizator din listă. Deci algoritmul dvs. nu a trebuit să se uite la fiecare intrare – l-a găsit la prima încercare. Algoritmul a luat O (n) timp? Sau a durat O (1) timp pentru că a găsit persoana aflată la prima încercare?

Căutarea simplă necesită în continuare O (n) timp. În acest caz, algoritmul a găsit instantaneu ce căuta. Acesta este cel mai bun scenariu. Notă Big O este despre cel mai rău caz scenariu. Deci, puteți spune asta, în cel mai rău caz, algoritmul va trebui să caute o dată prin fiecare utilizator din baza de date. Asta e O (n) timp. Este o asigurare – știți că căutarea simplă nu va fi niciodată mai lentă decât O (n) timp.

Unele perioade obișnuite de rulare Big O

1611645012 815 Notare O mare explicata simplu cu ilustratii si videoclipuri
Din xkcd. Dacă nu primiți gluma, aflați mai multe despre problema vânzătorului călător în cursul meu de la Manning Publications. 🙂

Iată cinci timpi de rulare Big O pe care îi vei întâlni foarte mult, sortați de la cel mai rapid la cel mai lent:

  • O (log n), de asemenea cunoscut ca si timp jurnal. Exemplu: Căutare binară.
  • O (n), de asemenea cunoscut ca si timpul liniar. Exemplu: căutare simplă.
  • O (n * Buturuga n). Exemplu: un algoritm de sortare rapidă, cum ar fi rapidul rapid.
  • O (n2). Exemplu: Un algoritm de sortare lent, cum ar fi sortarea de selecție.
  • O (n!). Exemplu: un algoritm foarte lent, cum ar fi vânzătorul de călătorii.

Vizualizarea diferitelor perioade de rulare Big O

1611645013 330 Notare O mare explicata simplu cu ilustratii si videoclipuri

Să presupunem că desenați o grilă de 16 cutii și puteți alege dintre 5 algoritmi diferiți pentru a face acest lucru. Dacă utilizați primul algoritm, vă va lua O (log n) timpul pentru a desena grila. Puteți face 10 operații pe secundă. Cu O (log n) timp, vă vor dura 4 operații pentru a desena o grilă de 16 casete (log 16 baza 2 este 4). Deci, vă va dura 0,4 secunde pentru a desena grila. Ce se întâmplă dacă trebuie să desenezi 1.024 de cutii? Vă va lua jurnal 1.024 = 10 operații sau 1 secundă pentru a desena o grilă de 1.024 cutii. Aceste numere utilizează primul algoritm.

Al doilea algoritm este mai lent: este nevoie de O (n) timp. Va fi nevoie de 16 operații pentru a extrage 16 cutii și va fi nevoie de 1.024 operațiuni pentru a extrage 1.024 cutii. Cât timp este în câteva secunde?

Iată cât ar dura pentru a desena o grilă pentru restul algoritmilor, de la cel mai rapid la cel mai lent:

1611645013 129 Notare O mare explicata simplu cu ilustratii si videoclipuri

Există și alte perioade de rulare, dar acestea sunt cele mai frecvente cinci.

Aceasta este o simplificare. În realitate, nu puteți converti de la un timp de rulare Big O la o serie de operații atât de bine, dar aceasta este o estimare bună.

Concluzie

Iată principalele mâncăruri de luat masa:

  • Viteza algoritmului nu se măsoară în secunde, ci în creșterea numărului de operații.
  • În schimb, vorbim despre cât de repede crește timpul de rulare al unui algoritm pe măsură ce crește dimensiunea intrării.
  • Durata de rulare a algoritmilor este exprimată în notația Big O.
  • O (log n) este mai rapid decât O (n), dar devine mult mai rapid pe măsură ce lista articolelor pe care le căutați crește.

Și iată un videoclip care acoperă o mulțime de ceea ce este în acest articol și multe altele.

Sper că acest articol v-a adus mai multă claritate despre notația Big O. Acest articol se bazează pe o lecție din cursul meu video de la Manning Publications Algoritmi în mișcare. Cursul se bazează pe uimitor carte Algoritmi Grokking de Adit Bhargava. El este cel care a desenat toate ilustrațiile distractive din acest articol.

Dacă înveți cel mai bine prin cărți, ia cartea! Dacă înveți cel mai bine prin videoclipuri, ia în considerare cumpărându-mi cursul. Puteți obține 39% reducere la cursul meu folosind codul ‘39carnes‘.