de Paul Rail

Tot ce trebuie să știți despre „Big O Notation” pentru a vă sparge următorul interviu de codare

Ca parte a educației mele de dezvoltare software, am trebuit să acumulez abilități în diferite domenii pentru a mă pregăti pe deplin pentru prima mea poziție software. Și orice program de educație software care își merită valoarea va include o porțiune corectă a curriculumului orientată spre pregătirea pentru interviul de codare infam.

Deci, în acest scop, la începutul fiecărei zile, Lucrez la rezolvarea algoritmilor, deoarece aceasta este o parte majoră (și pentru mulți partea cea mai dificilă) dintre cele mai multe interviuri de codificare.

Un lucru pe care l-am întâlnit în timp ce lucram la algoritmi de informatică este ceva numit „Notă O mare”.

Este un concept destul de abstract și foarte ezoteric de care marea majoritate a oamenilor nu vor auzi niciodată sau nu vor avea grijă. DAR este cunoscut ca fiind un întrebare comună de interviu de codificareși, prin urmare, este unul dintre lucrurile despre care am petrecut ceva timp învățând totul.

Ce trebuie sa stii

Iată ce am absorbit pentru a mă pregăti

Pentru a seta scena pentru „Big O”, trebuie mai întâi să recunoaștem acest lucru software-ul se bazează, desigur, foarte mult pe date. Munți uriași de date. Și folosirea acestor date este pentru ce este codarea. Pentru ca un program să poată utiliza datele, de multe ori trebuie să înceapă prin sortarea acestor date într-o ordine logică. Fie că este alfabetic, cronologic, după dimensiune, după dată și așa mai departe.

Triere se întâmplă CONSTANT, și de fapt reprezintă o porțiune imensă a tuturor activităților de computer și internet. Am auzit de programatori spunând că „Sortarea rapidă este destul de mult ceea ce rulează tot internetul”.

Ce înseamnă prin asta? Sortarea bine a datelor este întreaga sa subsecțiune în cadrul studiului informaticii și există mulți algoritmi bine definiți pentru sortare. Există Sortare rapidă, sortare cu bule, sortare prin selecție, sortare prin îmbinare, sortare prin grămadă si multe altele. Fiecare cu abordări diferite pentru a ajunge la rezultate identice sau similare.

Dar care este cel mai bun dacă (aproape) toate returnează același rezultat?

Cel mai bun înseamnă, de obicei, care este cel mai rapid. Aici a intrat în joc „Big O”.

Notare O mare, uneori numită și „analiză asimptotică”, în primul rând analizează câte operații ia un algoritm de sortare pentru a sorta complet o colecție foarte mare de date. Aceasta este o măsură a eficienței și este modul în care puteți compara direct un algoritm cu altul.

Când construiți o aplicație simplă cu doar câteva date pe care să le rezolvați, acest tip de analiză nu este necesar. Dar atunci când lucrați cu cantități foarte mari de date, cum ar fi un site de socializare sau un site mare de comerț electronic cu mulți clienți și produse, mici diferențe între algoritmi pot fi semnificative.

Notarea Big O clasifică eficiența algoritmilor

Face acest lucru cu privire la „O” și “n”, (Exemplu:„O (jurnal n) ”), Unde

• O se referă la ordinea funcției sau rata de creștere a acesteia și
• n este lungimea matricei de sortat.

Să analizăm un exemplu. Dacă un algoritm are numărul de operații cerute formula:

f(n) = 6n ^ 4 – 2n ^ 3 + 5

La fel de “n”Se apropie de infinit (pentru seturi foarte mari de date), dintre cei trei termeni prezenți, 6n ^ 4 este singurul care contează. Deci, termenii mai mici, 2n ^ 3 și 5, sunt de fapt doar omise pentru că sunt nesemnificative. Același lucru este valabil și pentru „6”În 6n ^ 4, de fapt.

Prin urmare, această funcție ar avea o rată de creștere a comenzii sau un rating „mare O” de O (n ^ 4).

Când ne uităm la mulți dintre cei mai frecvent utilizați algoritmi de sortare, ratingul de O (n jurnal n) în general este cel mai bun care poate fi atins. Algoritmii care rulează la această evaluare includ Sortare rapidă, Sortare în grămadă și Sortare în combinație. Sortare rapida este standard și este utilizat ca implicit în aproape toate limbile software.

Este important să rețineți că nu există un singur algoritm care să fie cel mai rapid în toate cazurile, deoarece datele pot fi introduse într-un program în toate modurile de state. Și abordările fiecărui algoritm vor avea cel mai bun caz și cel mai rău scenariu în care se comportă la cel mai bun sau la cel mai rău.

În timp ce Sortarea rapidă este standardul, concurează și cu Sortare Merge și Sortare Heap, care sunt alți algoritmi de sortare clasificați O (n log n). Există scenarii în care acestea sunt folosite în schimb.

Cel mai direct concurent al sortării rapide este Sortare în grămadă. Timpul de funcționare al sortării heap este, de asemenea, O (n jurnal n), dar timpul mediu de funcționare al sortării heap este considerat, de obicei, mai lent decât la sortarea rapidă la fața locului.

Merge Sort este un sort stabil, ceea ce înseamnă că păstrează ordinea de intrare a elementelor egale în ieșire, spre deosebire de Sortare rapidă standard și Sortare Heap.

Balon / Inserare / Selecție Sortare rulare la O (n²), care în ceea ce privește numărul de operațiuni poate dura mult mai mult decât cele enumerate mai sus cotate la O (n log n) atunci când se ocupă de date cu adevărat mari. Dar pot exista scenarii în care celelalte sunt mai rapide în funcție de date.

Există, de asemenea, momente în care ceva foarte simplu, cum ar fi Numărarea sortării, este extraordinar, deoarece este mult mai rapid de scris și mult mai ușor de vizualizat și de înțeles.

Uneori nu trebuie doar să luați în considerare cerințele de timp ale unui algoritm, ci și cerințele de spațiu de date (sau poate chiar mai mult). Unii algoritmi funcționează și cu o amprentă de stocare mai mică.

De ce trebuie să știi toate acestea?

Deci, după toate acestea, dacă întotdeauna recurgi la utilizarea algoritmului de sortare încorporat al unui limbaj (care se bazează pe Sortare rapidă), atunci de ce să-ți pese de algoritmi de sortare și „Big O”? De ce v-ar întreba companiile despre asta într-un interviu?

Răspunsul este că studierea notării Big O te face să înțelegi conceptul foarte important al eficienței în codul tău. Deci, atunci când lucrați cu seturi de date uriașe, veți avea o bună înțelegere a locurilor în care încetinirile majore pot provoca blocaje și unde ar trebui acordată o atenție sporită pentru a obține cele mai mari îmbunătățiri. Aceasta se numește, de asemenea, analiza sensibilității și este o parte importantă a rezolvării problemelor și a scrierii unui software excelent.

Deci, dacă încercați să vă pregătiți pentru primul dvs. interviu sau poate că v-ați chinuit în ultimul dvs., creșterea cunoștințelor dvs. despre concepte precum Notarea Big O și alte subiecte de informatică vă vor ajuta să vă ajutați. Veți fi mai bine echipat pentru a vă demonstra potențialul și a impresiona pentru a obține acea poziție.