Složenost jednostavnih algoritama i struktura podataka u JS-u

U prethodnom članku “Korak prema računarstvu kao znanosti: jednostavni algoritmi i strukture podataka u JS-u”, raspravljali smo o jednostavnim algoritmima (linearna i binarna pretraživanja; oblačići, sortiranje odabira i umetanja) i strukturi podataka (upareni objekti polja i ključa / vrijednosti. ). Ovdje nastavljam s konceptom složenosti i njegovom primjenom na ove algoritme i strukture podataka.

Složenost

Složenost je čimbenik koji je uključen u složeni proces. Što se tiče algoritama i struktura podataka, to može biti vrijeme ili prostor (što znači računalna memorija) potreban za obavljanje određenog zadatka (pretraživanje, sortiranje ili pristup podacima) na datoj strukturi podataka. Učinkovitost izvršavanja zadatka ovisi o broju operacija potrebnih za izvršavanje zadatka.

Iznošenje smeća može zahtijevati 3 koraka (vezivanje vreće za smeće, iznošenje van i bacanje u kontejner). Iznošenje smeća može biti jednostavno, ali ako iznosite smeće nakon dugog tjedna obnove, možda nećete moći izvršiti zadatak zbog nedostatka prostora u kontejneru.

Usisavanje prostorije može zahtijevati mnogo koraka koji se ponavljaju (uključivanje, opetovano pometanje glave usisavača po podu i isključivanje). Što je prostorija veća, to ćete više puta morati pomaknuti glavu usisavača po podu. Dakle, što je duže potrebno vrijeme za usisavanje prostorije.

Dakle, postoji izravna uzročno-posljedična veza između broja izvedenih operacija i broja elemenata koji se izvode. Ako imate puno smeća (elemenata), potrebno ga je iznijeti mnogo puta. To može dovesti do problema složenosti prostora . Imati puno kvadratnih metara (elemenata) zahtijeva višestruko pometanje glave usisavača po podu. To može dovesti do problema vremenske složenosti .

Bilo da iznosite smeće ili usisavate sobu , mogli biste reći da se broj operacija ( O ) točno povećava s brojem elemenata ( n ) . Ako imam 1 vreću za smeće, smeće moram jednom iznijeti. Ako sam imao 2 vreće za smeće, isti zadatak moram obaviti dva puta, pod pretpostavkom da fizički ne možete odjednom podići više vreća. Dakle, Big-O ovih poslova je O = n ili O = funkcija (n) ili O (n) . To je linearna složenost (ravna crta s 1 operacijom: 1 korespondencija elementa). Dakle, izvodi se 30 operacija na 30 elemenata (žuta crta na grafikonu).

To je slično onome što se događa kada se razmatraju algoritmi i strukture podataka.

Pretrage

Linearno pretraživanje

Najboljem slučaju za pretraživanje stavke poredane liste, jedna za drugom, stalni je O (1) , uz pretpostavku da je prvi predmet na popisu. Dakle, ako je stavka koju tražite uvijek navedena prva, bez obzira na veličinu popisa, stavku ćete pronaći u trenu. Složenost pretraživanja konstantna je s veličinom popisa. Prosjeku najgorem slučaju ove vrste pretraživanja je linearna složenost ili O (n). Drugim riječima,za n stavki moram pogledati n puta, prije nego što pronađem svoju stavku, dakle linearno pretraživanje.

Binarno pretraživanje

Za binarno pretraživanje najbolji je slučaj O (1), što znači da se stavka vašeg pretraživanja nalazi u središnjoj točki. Najgorem slučaju prosjek i je log baze 2 n ili:

Logaritam ili zapis je način izražavanja eksponenta za datu bazu. Dakle, ako postoji 16 elemenata (n = 16), tada bi bila potrebna, u najgorem slučaju, 4 koraka za pronalaženje broja 15 (eksponent = 4).

Ili jednostavno: O (log n)

Vrsta

Mjehurić

U razvrstavanju mjehurića, svaki se predmet uspoređuje s ostatkom zbirke kako bi se odredila najviša vrijednost za stvaranje oblačića. Iz tog razloga je njegova složenost u prosjeku do najgoreg slučaja O (n²) . Razmislite o petlji ugniježđenoj unutar druge petlje.

Dakle, za svaku stavku uspoređujete je s ostatkom svoje kolekcije. To iznosi 16 usporedbi (ili operacija) za 4 elementa (4² = 16). Najboljem slučaju je li vaš zbirka je gotovo riješeno, osim za jednu stavku. To bi značilo jedan krug usporedbi. Odnosno, potrebne su četiri usporedbe da bi se član kolekcije od četiri predmeta stvorio u mjehuriće, što je složenost O (n) .

Izbor

Za razliku od sortiranja mjehurića , umjesto baloniranja najveće vrijednosti, selekcijsko sortiranje odabire najnižu vrijednost da bi je zamijenilo na najranije pozicije. No, budući da zahtijeva usporedbu svake stavke s ostatkom zbirke, također ima složenost O (n²) .

Umetanje

Za razliku od sortiranja oblačića i odabira , sortiranje umetanjem umetće predmet u njegov ispravan položaj. Ali, kao i prethodne vrste, to također zahtijeva usporedbu svake stavke s ostatkom zbirke, stoga ima prosječnu i najgoru složenost O (n²) . Poput razvrstavanja u oblačiću , ako je za sortiranje preostala samo jedna stavka, potreban je samo jedan krug usporedbe kako bi se stavka stavila na pravilan položaj. Odnosno, ima najbolju složenost slova O (n) .

Strukture podataka

Nizovi

Budući da je potreban jedan korak za pristup stavci niza putem njegovog indeksa ili dodavanje / uklanjanje stavke na kraju niza, složenost pristupa , guranja ili iskakanja vrijednosti u nizu je O (1) . Dok linearno pretraživanje niza preko njegovog indeksa, kao što je već viđeno, ima složenost O (n) .

Također, budući da pomak ili pomicanje vrijednosti na ili s prednje strane niza zahtijeva reindeksiranje svakog elementa koji ga slijedi (tj. Uklanjanje elementa u indeksu 0 zahtijeva ponovno označavanje elementa u indeksu 1 kao indeksa 0 i tako dalje), oni imaju složenost O (n) . Ponovno označavanje provodi se od početka do kraja niza.

Ključ - vrijednost uparenih objekata

Pristup , umetanje ili uklanjanje vrijednosti pomoću ključa je trenutni, pa imaju složenost O (1) . Pretraživanje određenog predmeta pomoću svakog dostupnog ključa kroz svaki "polog" u osnovi je linearno pretraživanje . Dakle, ima složenost O (n) .

Zaključak

Složenost je više od samo teme za raspravu o uspostavljenim algoritmima i strukturama podataka. Ako se pametno koristi, to može biti koristan alat za procjenu učinkovitosti vašeg posla i koda koji stvarate za rješavanje vaših problema.

Referenca:

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