de Yung L. Leung

Complexitatea algoritmilor simpli și a structurilor de date din JS

Complexitatea algoritmilor simpli si a structurilor de date din JS
Fotografie de Karsten Würth pe Unsplash

În articolul precedent „Un pas către computere ca știință: algoritmi simpli și structuri de date în JS”, Am discutat despre algoritmi simpli (căutări liniare și binare; sortare cu bule, selecție și inserție) și structuri de date (obiecte asociate matrice și cheie-valoare). Aici, continui cu conceptul de complexitate și aplicarea acestuia la acești algoritmi și structuri de date.

Complexitate

Complexitate este un factor implicat într-un proces complex. În ceea ce privește algoritmii și structurile de date, acesta poate fi timp sau spaţiu (adică memorie de calcul) necesară pentru efectuarea unei sarcini specifice (căutare, sortare sau acces la date) pe o anumită structură de date. Eficiența efectuării unei sarcini depinde de numărul de operații necesare pentru a finaliza o sarcină.

Ducând gunoiul afară poate necesita 3 pași (legarea unui sac de gunoi, aducerea acestuia în afară și aruncarea într-un tomberon). Ducând gunoiul afară poate fi simplu, dar dacă scoateți coșul de gunoi după o săptămână lungă de renovare, s-ar putea să vă aflați în imposibilitatea de a finaliza sarcina din cauza unei lipsa de spatiu în tomberon.

Aspirarea unei camere poate necesita mulți pași repetitivi (pornirea acestuia, măturarea repetată a capului de vid pe o podea și oprirea acestuia). Cu cât o cameră este mai mare, cu atât mai multe ori va trebui să măturați un cap de vid pe podea. Astfel, mai mult timp va fi nevoie pentru a aspira camera.

Complexitatea algoritmilor simpli si a structurilor de date din JS

Deci, există o relație de cauzalitate directă între numărul de operații efectuate și numărul de elemente care sunt efectuate. A avea o mulțime de gunoi (elemente) necesită scoaterea acestuia de multe ori. Acest lucru poate duce la o problemă de complexitatea spațiului. Pentru a avea o mulțime de metri pătrați (elemente), este necesar să măturați de multe ori un cap de vid pe podea. Acest lucru poate duce la o problemă de complexitatea timpului.

Fie că ești ducând gunoiul afară sau aspirând o cameră, s-ar putea spune că număr de operații (O) crește exact odată cu numărul de elemente (n). Dacă am 1 geantă de gunoi, trebuie să scot gunoiul o dată. Dacă aveam 2 saci de gunoi, trebuie să îndeplinesc aceeași sarcină de două ori, presupunând că fizic nu poți ridica mai multe saci la un moment dat. Deci, Big-O al acestor treburi este O = n sau O = funcție (n) sau Pe). Aceasta este o complexitate liniară (o linie dreaptă cu o operație 1: corespondență 1 element). Deci, 30 de operații sunt efectuate pe 30 de elemente (linia galbenă pe grafic).

Acest lucru este similar cu ceea ce se întâmplă atunci când se iau în considerare algoritmi și structuri de date.

Căutări

Complexitatea algoritmilor simpli si a structurilor de date din JS
sursă

cel mai bun caz căutarea unui articol dintr-o listă ordonată, una după alta, este o constantă O (1), presupunând că este primul articol din lista dvs. Deci, dacă elementul pe care îl căutați este întotdeauna listat primul, indiferent de dimensiunea listei, veți găsi articolul într-o clipă. Complexitatea căutării dvs. este constantă cu dimensiunea listei. medie la cel mai rău caz a acestui tip de căutare este o complexitate liniară sau Pe). Cu alte cuvinte, pentru n articole, trebuie să caut de n ori, înainte să-mi găsesc articolul, deci căutare liniară.

1612166587 988 Complexitatea algoritmilor simpli si a structurilor de date din JS
sursă

Pentru o căutare binară, cel mai bun caz este O (1), ceea ce înseamnă că elementul căutării dvs. este situat în punctul mediu. cel mai rău și mediu caz este baza log 2 a lui n sau:

1612166587 298 Complexitatea algoritmilor simpli si a structurilor de date din JS

Logaritmul sau jurnalul este un mod de a exprima un exponent pentru o bază dată. Deci, dacă ar exista 16 elemente (n = 16), atunci ar fi nevoie, în caz mai rău, de 4 pași pentru a găsi numărul 15 (exponent = 4).

1612166587 57 Complexitatea algoritmilor simpli si a structurilor de date din JS

Sau pur și simplu: O (jurnal n)

1612166588 734 Complexitatea algoritmilor simpli si a structurilor de date din JS

Sortează

Bubble

1612166588 37 Complexitatea algoritmilor simpli si a structurilor de date din JS
sursă

În sortarea cu bule, fiecare articol este comparat cu restul colecției pentru a determina cea mai mare valoare de bule. Din acest motiv, pe medie la cel mai rău caz, complexitatea sa este O (n²). Gândiți-vă la o buclă imbricată într-o altă buclă.

1612166588 375 Complexitatea algoritmilor simpli si a structurilor de date din JS

Deci, pentru fiecare articol, îl comparați cu restul colecției. Aceasta se ridică la 16 comparații (sau operații) pentru 4 elemente (4² = 16). cel mai bun caz este dacă colecția dvs. este aproape sortată, cu excepția unui singur articol. Aceasta ar însemna o singură rundă de comparații. Adică, sunt necesare patru comparații pentru a crea un membru al unei colecții cu patru articole, ceea ce reprezintă o complexitate Pe).

Selecţie

1612166588 653 Complexitatea algoritmilor simpli si a structurilor de date din JS
sursă

Spre deosebire de sortare cu bule, în loc să clocotească cea mai mare valoare, sortare de selecție selectează cea mai mică valoare pentru a o schimba în primele poziții. Dar, deoarece necesită compararea fiecărui articol cu ​​restul colecției, are și o complexitate de O (n²).

Inserare

1612166589 549 Complexitatea algoritmilor simpli si a structurilor de date din JS
sursă

spre deosebire de balon & tipuri de selecție, sortare inserție introduce elementul în poziția corectă. Dar, ca și sortimentele anterioare, acest lucru necesită și compararea fiecărui articol cu ​​restul colecției, prin urmare, are un medie la cel mai rău caz complexitatea O (n²). Ca sortare cu bule, dacă rămâne un singur articol de sortat, este nevoie doar de o singură rundă de comparații pentru a insera articolul în poziția corectă. Adică are cel mai bun caz complexitatea Pe).

Structuri de date

Matrice

1612166589 254 Complexitatea algoritmilor simpli si a structurilor de date din JS

Deoarece este nevoie de un singur pas pentru a accesa un element dintr-un tablou prin indexul acestuia sau pentru a adăuga / elimina un articol la sfârșitul unui tablou, complexitatea pentru accesând, împingând sau popping o valoare într-o matrice este O (1). Întrucât, căutând liniar printr-o matrice prin indexul său, așa cum s-a văzut mai înainte, are o complexitate de Pe).

De asemenea, pentru că a schimb sau neschimbată a unei valori către sau din fața unui tablou necesită reindexare fiecare element care îl urmează (adică eliminarea unui element la indexul 0 necesită reetichetarea elementului la indexul 1 ca index 0 și așa mai departe), au o complexitate de Pe). Reetichetarea se efectuează de la începutul până la sfârșitul matricei.

Obiecte pereche cheie – valoare

1612166590 456 Complexitatea algoritmilor simpli si a structurilor de date din JS
sursă

Accesarea, inserarea sau îndepărtarea o valoare prin utilizarea unei chei este instantanee și, prin urmare, au o complexitate de O (1). Căutarea în fiecare „cutie de depozit” pentru un anumit articol folosind fiecare cheie disponibilă este în esență o căutare liniară. Așadar, are o complexitate de Pe).

Concluzie

Complexitate este mai mult decât un subiect pentru discutarea algoritmilor stabiliți și a structurilor de date. Dacă este utilizat cu înțelepciune, poate fi un instrument util pentru măsurarea eficienței muncii pe care o faceți și a codului pe care îl creați pentru a vă rezolva problemele.

Referinţă:

https://www.udemy.com/js-algorithms-and-data-structures-masterclass/