Yksinkertaisten algoritmien ja tietorakenteiden monimutkaisuus JS: ssä

Edellisessä artikkelissa "Askel kohti tietojenkäsittelyä tieteenä: Yksinkertaiset algoritmit ja tietorakenteet JS: ssä" keskustelimme yksinkertaisista algoritmeista (lineaariset ja binaarihaut; kupla-, valinta- ja lisäyslajitteet) ja tietorakenteista (taulukko ja avainarvoparitetut objektit) ). Jatkan tässä monimutkaisuuden käsitettä ja sen soveltamista näihin algoritmeihin ja tietorakenteisiin.

Monimutkaisuus

Monimutkaisuus on tekijä, joka liittyy monimutkaiseen prosessiin. Mitä tulee algoritmeihin ja tietorakenteisiin, tämä voi olla aika tai tila (eli laskennallinen muisti), joka tarvitaan tietyn tehtävän suorittamiseen (tietojen haku, lajittelu tai pääsy tietylle tietorakenteelle). Tehtävän suorittamisen tehokkuus riippuu tehtävän suorittamiseen tarvittavien toimintojen määrästä.

Roskakorin vieminen voi vaatia 3 vaihetta (roskasäkin sitominen, tuominen sen ulkopuolelle ja pudottaminen kaatopaikalle). Roskakorin poistaminen voi olla yksinkertaista, mutta jos viet roskakorin pitkän viikon remontin jälkeen, saatat huomata, että et pysty suorittamaan tehtävää, koska kaatopaikassa ei ole tilaa .

Huoneen imurointi voi vaatia monia toistuvia vaiheita (virran kytkeminen päälle, imupään toistuva pyyhkäisy lattian yli ja sammuttaminen). Mitä suurempi huone, sitä useammin sinun on lakaistava tyhjiöpää sen lattian yli. Siksi, mitä kauemmin huoneen imurointi kestää.

Joten suoritettujen toimintojen ja suoritettavien elementtien lukumäärän välillä on suora syy-yhteys. Paljon roskaa (elementtejä) edellyttää sen poistamista monta kertaa. Tämä voi johtaa avaruuden monimutkaisuuteen . Paljon neliömetriä (elementtejä) vaatii alipainepään lakaistamisen kerroksen yli monta kertaa. Tämä voi johtaa ajan monimutkaisuuteen .

Otatpa roskakorin pois tai imetät huoneen , saatat sanoa, että toimintamäärä ( O ) kasvaa tarkalleen elementtien lukumäärän ( n ) kanssa . Jos minulla on yksi roskapussi, minun on vietävä roskakori kerran. Jos minulla oli 2 roskapussia, minun on suoritettava sama tehtävä kahdesti, olettaen, ettet fyysisesti pysty nostamaan enempää kuin yhden pussin kerrallaan. Joten näiden askareiden Big-O on O = n tai O = funktio (n) tai O (n) . Tämä on lineaarinen monimutkaisuus (suora viiva 1 operaatio: 1 elementin vastaavuus). Joten 30 toimintoa suoritetaan 30 elementillä (keltainen viiva kaaviossa).

Tämä on samanlainen kuin mitä tapahtuu, kun otetaan huomioon algoritmit ja tietorakenteet.

Haut

Lineaarinen haku

Parhaassa tapauksessa hakemiseksi kohteen järjestettyä luetteloa, yksi toisensa jälkeen, on vakio O (1) , jos se on 1. erä luetteloon. Joten jos etsimäsi kohde on aina luettelossa ensin luettelosi koosta riippumatta, löydät tuotteesi hetkessä. Haun monimutkaisuus on vakio luettelon koon kanssa. Keskiarvon pahimmassa tapauksessa tällainen haku on lineaarinen monimutkaisuus tai O (n). Toisin sanoen,n kohteen kohdalla minun on etsittävä n kertaa, ennen kuin löydän tuotteeni, siis lineaarinen haku.

Binaarihaku

Binaarihakua varten paras tapa on O (1), eli haun kohde sijaitsee keskipisteessä. Huonoin ja keskimääräisestä tapauksesta on log2 n tai:

Logaritmi tai loki on tapa ilmaista eksponentti tietylle perustalle. Joten, jos elementtejä olisi 16 (n = 16), niin pahemmassa tapauksessa vie neljä vaihetta luvun 15 (eksponentti = 4) löytämiseksi.

Tai yksinkertaisesti: O (log n)

Lajittelee

Kupla

Kuplalajittelussa jokaista tuotetta verrataan muuhun kokoelmaan suurimman kuplittuvan arvon määrittämiseksi. Tästä syystä keskimäärin pahimpaan tapaan sen monimutkaisuus on O (n²) . Ajattele toisen silmukan sisällä olevaa silmukkaa.

Joten verrataan kutakin tuotetta muuhun kokoelmaasi. Tämä tarkoittaa 16 vertailua (tai operaatiota) 4 elementille (4 = = 16). Parhaassa tapauksessa on, jos kokoelma on lähes lajitellaan, paitsi yksittäisen kohteen. Tämä merkitsisi yhtä vertailukierrosta. Toisin sanoen vaaditaan neljä vertailua neljän kohteen kokoelman jäsenen kuplittamiseksi, mikä on O (n): n monimutkaisuus .

Valinta

Toisin kuin kuplalajittelu , korkeimman arvon kuplittamisen sijaan valintalajittelu valitsee pienimmän arvon vaihtaakseen sen aikaisimpiin paikkoihin. Mutta koska se vaatii jokaisen kohteen vertaamista muuhun kokoelmaan, sillä on myös monimutkaisuus O (n²) .

Lisäys

Toisin kuin kupla- ja valintalajit , lisäyslaji lisää kohteen oikeaan paikkaan. Mutta, kuten edellinen lajittelee, tämä edellyttää myös vertaamalla kunkin kohteen muuhun keräämiseen, joten se on keskimäärin pahin monimutkaisuuden O (n²) . Kuplalajittelun tavoin , jos lajittelemiseen on jäljellä vain yksi kohde, kohteen lisääminen oikeaan paikkaan vaatii vain yhden vertailukierroksen. Toisin sanoen sillä on parhaan tapauksen O (n) monimutkaisuus .

Tietorakenteet

Taulukot

Koska se ottaa yhden askeleen käyttää kohdetta array kautta sen indeksi, tai lisätä / poistaa tuotteen lopussa array, mutkikkuus päästä , työntää tai Shooter arvo joukko on O (1) . Ottaa huomioon, lineaarisesti etsimällä joukon kautta kautta sen indeksi, kuten nähdään aikaisemmin, on monimutkaisuus O (n) .

Myös, koska muutos tai unshift , joiden arvo tai edestä array edellyttää Uudelleenindeksointi kukin elementti, joka seuraa sitä (eli poistamalla elementin indeksi 0 edellyttää uudelleenmerkinnöistä elementin indeksi 1, kun indeksi on 0, ja niin edelleen), niillä on O: n (n) monimutkaisuus . Uudelleenmerkintä suoritetaan matriisin alusta loppuun.

Avainarvo paritetut objektit

Arvoon pääsy , sen lisääminen tai poistaminen avainta käyttämällä on välitöntä, joten niiden monimutkaisuus on O (1) . Tietyn kohteen jokaisen “talletuslaatikon” etsiminen käyttämällä kaikkia käytettävissä olevia avaimia on pohjimmiltaan lineaarinen haku . Ja niin, sillä on O (n): n monimutkaisuus .

Johtopäätös

Monimutkaisuus on enemmän kuin vain aihe vakiintuneiden algoritmien ja tietorakenteiden keskustelemiseksi. Jos sitä käytetään viisaasti, se voi olla hyödyllinen työkalu tekemäsi työn ja tehokkaan koodin määrittämiseen ongelmiesi ratkaisemiseksi.

Viite:

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