Az egyszerű algoritmusok és adatstruktúrák összetettsége a JS-ben

Az előző cikkben „Lépés a számítástechnika felé mint tudomány: egyszerű algoritmusok és adatstruktúrák a JS-ben” egyszerű algoritmusokat (lineáris és bináris keresések; buborék-, kijelölési és beillesztési sorrendek) és adatstruktúrákat (tömb és kulcsérték párosított objektumok) tárgyaltunk. ). Itt folytatom a komplexitás fogalmát és alkalmazását ezekre az algoritmusokra és adatstruktúrákra.

Bonyolultság

A komplexitás egy összetett folyamatban részt vevő tényező. Az algoritmusokat és adatstruktúrákat tekintve ez lehet az idő vagy a tér (vagyis a memória kiszámítása), amely egy adott feladat struktúrájához (adatok keresése, rendezése vagy elérése) szükséges egy adott adatstruktúrán. A feladat végrehajtásának hatékonysága a feladat elvégzéséhez szükséges műveletek számától függ.

A szemét elszállításához 3 lépésre lehet szükség (egy szemeteszsák felkötése, kifelé juttatása és szemetesbe dobása). Lehet, hogy a kuka kivitele egyszerű, de ha egy hosszú felújítási hét után kiveszi a szemetet, előfordulhat, hogy a szemetesben hiányos hely miatt képtelen lesz elvégezni a feladatot .

A helyiség porszívózása sok ismétlődő lépést igényelhet (bekapcsolása, a vákuumfej többszöri átmosása a padlón és kikapcsolása). Minél nagyobb egy szoba, annál többször kell vákuumfejet söpörnie a padlón. Így minél hosszabb ideig tart a szoba elszívása.

Tehát közvetlen oksági kapcsolat van az elvégzett műveletek száma és a végrehajtott elemek száma között. A sok szemetet (elemet) sokszor ki kell venni. Ez a tér összetettségének problémájához vezethet . Sok négyzetméter (elem) birtoklásához sokszor át kell söpörni a vákuumfejet a padlón. Ez az idő összetettségének problémájához vezethet .

Akár kiveszi a szemetet, akár egy helyiséget porszívózik , azt mondhatja, hogy a műveletek száma ( O ) pontosan növekszik az elemek számával ( n ) . Ha van 1 szemeteszsákom, egyszer ki kell vennem a szemetet. Ha 2 szemeteszsákom volt, akkor kétszer kell elvégeznem ugyanazt a feladatot, feltételezve, hogy fizikailag nem emelhet fel egynél több zsákot egyszerre. Tehát ezen házimunkák Big-O értéke O = n vagy O = függvény (n) vagy O (n) . Ez egy lineáris összetettség (egyenes vonal 1 művelettel: 1 elem megfelelőséggel). Tehát 30 műveletet hajtunk végre 30 elemen (sárga vonal a grafikonon).

Ez hasonló ahhoz, ami az algoritmusok és adatstruktúrák mérlegelésekor történik.

Keresések

Lineáris keresés

A sorrendben szereplő elemek egymás után történő keresésének legjobb esete egy állandó O (1) , feltéve, hogy ez a lista első eleme. Tehát, ha a keresett elem mindig a listán szerepel, függetlenül a lista méretétől, akkor egy pillanat alatt megtalálja az elemét. A keresés összetettsége állandó a lista méretével. Az ilyen típusú keresések átlaga a legrosszabb esetben lineáris komplexitás vagy O (n). Más szavakkal,n tétel esetén n-szer meg kell néznem, mielőtt megtalálom az elememet, ezért lineáris keresés.

Bináris keresés

Bináris keresés esetén a legjobb eset az O (1), vagyis a keresés eleme a középpontban található. A legrosszabb és átlagos eset az n 2. log alapja vagy:

A logaritmus vagy a napló egy exponens kifejeződésének módja egy adott bázishoz. Tehát, ha 16 elem lenne (n = 16), akkor rosszabb esetben 4 lépésre lenne szükség a 15-ös szám megtalálásához (kitevő = 4).

Vagy egyszerűen: O (log n)

Rendezés

Buborék

Buborékos rendezésben minden elemet összehasonlítanak a gyűjtemény többi részével, hogy meghatározzák a legmagasabb értéket. Emiatt átlagosan a legrosszabb esetben komplexitása O (n²) . Gondolj egy másik hurokba beágyazott hurokra.

Tehát minden elemhez összehasonlítja a gyűjtemény többi részével. Ez 4 elem (16 = 16) 16 összehasonlítását (vagy műveletét) jelenti. A legjobb eset , ha a gyűjteményed szinte rendezve van, kivéve egyetlen elemet. Ez egyetlen összehasonlítási kört jelentene. Vagyis négy összehasonlításra van szükség ahhoz, hogy egy négy tételből álló gyűjtemény tagját kibillentse, ami O (n) összetettsége .

Kiválasztás

A buborék-rendezéssel ellentétben a legmagasabb érték buborékosítása helyett a választási rendezés a legalacsonyabb értéket választja, hogy a legkorábbi pozíciókra cserélje. Mivel azonban minden elemet össze kell hasonlítani a gyűjtemény többi részével, O (n²) összetettsége is van .

Beszúrás

Ellentétben a buborék és kiválasztási fajta , behelyezés sort szúr a tételt a megfelelő helyzetbe. De, hasonlóan a korábbi fajtákhoz, ehhez is meg kell hasonlítani az egyes tételeket a gyűjtemény többi részével, ezért az O (n²) átlagos és a legrosszabb esetben is összetett . A buborék-rendezéshez hasonlóan , ha csak egy elem van hátra a rendezéshez, csak egyetlen összehasonlítási körre van szükség ahhoz, hogy az elemet a megfelelő helyzetébe illessze. Vagyis a legjobb esetben az O (n) komplexitása van .

Adatszerkezetek

Tömbök

Mert tart egy lépésben hozzáférni egy elemet a tömb keresztül index, vagy hozzáadni / eltávolítani egy elemet a végén egy tömb, az összetettsége elérésével , toló vagy popping egy értéket a tömb O (1) . Míg az indexen keresztül lineárisan keresve egy tömböt, amint azt korábban láttuk, O (n) összetettsége van .

Továbbá, mivel az érték eltolásához vagy eltolásához egy tömb elejére vagy onnan meg kell követni az egyes elemeket, amelyek azt követik (vagyis ha egy elemet eltávolítunk a 0. indexből, akkor az 1. indexen új elemet kell jelölni, mint 0. indexet, stb.) O (n) komplexitása . Az átcímkézés a tömb elejétől a végéig tart.

Kulcsérték párosított objektumok

Az érték elérése , beszúrása vagy eltávolítása egy kulcs használatával pillanatnyi, így O (1) összetettsége van . Az egyes „betétdobozokban” való keresés minden rendelkezésre álló kulcs használatával lényegében lineáris keresés . Tehát, O (n) összetettsége van .

Következtetés

A komplexitás nem csupán téma a bevált algoritmusok és adatstruktúrák megvitatására. Ha okosan használják, akkor hasznos eszköz lehet az elvégzett munka hatékonyságának és a probléma megoldására létrehozott kód felméréséhez.

Referencia:

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