logo

TechCodeview

Opi tietorakenteet ja algoritmit | DSA opetusohjelma

Tietorakenteet ja algoritmit (DSA) viittaavat tiedon organisointi- ja tallennusmenetelmien tutkimiseen sekä näillä tietorakenteilla toimivien ongelmien ratkaisumenettelyjen (algoritmien) suunnitteluun. DSA on yksi tärkeimmistä taidoista, joka jokaisen tietojenkäsittelytieteen opiskelijan tulee olla. Usein nähdään, että ihmiset, joilla on hyvät tiedot näistä teknologioista, ovat parempia ohjelmoijia kuin muut ja murtavat siten lähes jokaisen teknologiajätin haastattelut. Tämä DSA opetusohjelma tavoitteena on auttaa sinua oppimaan tietorakenteet ja -algoritmit (DSA) nopeasti ja helposti.



Sisällysluettelo

  • Opi algoritmit
  • Opi monimutkaisuuksista
  • Harjoittele ongelmahuijauslehtiä

    • DSA täysi lomake

    Termi DSA tarkoittaa Tietorakenteet ja algoritmit , tietojenkäsittelytieteen yhteydessä.

    Mikä on DSA?

    Tietorakenteet ja algoritmit (DSA) viittaavat tiedon organisointi- ja tallennusmenetelmien tutkimiseen sekä näillä tietorakenteilla toimivien ongelmien ratkaisumenettelyjen (algoritmien) suunnitteluun.



    Kuinka oppia DSA?

    Ensimmäinen ja tärkein asia on jakaa koko toimenpide pieniin osiin, jotka on tehtävä peräkkäin. Koko prosessi DSA:n oppimiseksi tyhjästä voidaan jakaa viiteen osaan:

    1. Opi ainakin yksi ohjelmointikieli (jätämme tämän valinnallesi.)
    2. Opi tietorakenteet
    3. Opi algoritmit
    4. Opi ajan ja tilan monimutkaisuudesta
    5. Harjoitusongelmat DSA:ssa
    Kuinka oppia DSA?

    Kuinka oppia DSA?

    Toivoen, että olet oppinut valitsemasi ohjelmointikielen, siirrymme seuraavaan vaiheeseen DSA:n oppimiseksi tässä DSA-opetusohjelmassa.



    Tässä tulee tietorakenteen ja algoritmin oppimisen tiekartan tärkein ja odotetuin vaihe – vaihe, jossa aloitat DSA:n oppimisen. DSA-aihe koostuu kahdesta osasta:

    • Tietorakenteet
    • Algoritmit

    Vaikka ne ovat kaksi eri asiaa, ne liittyvät vahvasti toisiinsa, ja on erittäin tärkeää seurata oikeaa tietä oppiaksesi ne tehokkaimmin. Jos olet epävarma siitä, kumpi oppia ensin, suosittelemme, että käyt läpi yksityiskohtaisen analyysimme aiheesta: Tässä olemme seuranneet tietorakenteen oppimisen kulkua ja sitten siihen liittyviä ja tärkeimpiä algoritmeja, joita tietorakenne käyttää.

    Opi tietorakenteet

    Tietorakenteet ovat tärkeitä komponentteja, jotka auttavat järjestämään ja tallentamaan tietoja tehokkaasti tietokoneen muistiin. Ne tarjoavat tavan hallita ja käsitellä tietoja tehokkaasti, mikä mahdollistaa nopeamman pääsyn, lisäys- ja poistotoiminnot. Yleisiä tietorakenteita ovat mm taulukot, linkitetyt luettelot, pinot, jonot, puut ja kaaviot , joista jokainen palvelee tiettyjä tarkoituksia käsiteltävän ongelman vaatimusten perusteella. Tietorakenteiden ymmärtäminen on olennaista tehokkaiden algoritmien suunnittelussa ja ohjelmiston suorituskyvyn optimoinnissa.

    Array on lineaarinen tietorakenne, joka tallentaa kokoelman saman tietotyypin elementtejä. Elementeille on varattu jatkuva muisti, mikä mahdollistaa jatkuvan käytön. Jokaisella elementillä on yksilöllinen indeksinumero.

    • Toiminnot Arraylla:
      • Läpikulku : Iterointi taulukon elementtien läpi.
      • Lisäys : Elementin lisääminen taulukkoon tietyssä indeksissä.
      • Poistaminen : Elementin poistaminen taulukosta tietyssä indeksissä.
      • Etsitään : Elementin etsiminen taulukosta sen arvon tai indeksin perusteella.
    • Taulukkotyypit :
      • Yksiulotteinen matriisi : Yksinkertainen taulukko, jossa on yksi ulottuvuus.
      • Moniulotteinen taulukko : Matriisi, jossa on useita ulottuvuuksia, kuten matriisi.
    • Array-sovellukset :
      • Tietojen tallentaminen peräkkäin
      • Jonojen, pinojen ja muiden tietorakenteiden toteuttaminen
      • Edustavat matriiseja ja taulukoita
    • Aiheeseen liittyviä aiheita Arrayssa:
      • Arrays opetusohjelma
      • 50 suosituinta taulukon koodausongelmaa haastatteluissa
      • Harjoittele ongelmia Arraysissa

    2. merkkijono

    A merkkijono on merkkijono, jota käytetään tyypillisesti tekstin esittämiseen. Sitä pidetään tietotyyppinä, joka mahdollistaa tekstitietojen käsittelyn ja käsittelyn tietokoneohjelmissa.

    • Toiminnot merkkijonolla :
      • Yhdistäminen : Kahden merkkijonon yhdistäminen.
      • Vertailu : Kahden merkkijonon vertailu leksikografisesti.
      • Alimerkkijono uuttaminen : Osamerkkijonon purkaminen merkkijonosta.
      • Hae : Etsitään alimerkkijonoa merkkijonosta.
      • Muokkaus : Merkkien muuttaminen tai korvaaminen merkkijonossa.
    • Stringin sovellukset :
      • Tekstinkäsittely
      • Kuvioiden yhteensopivuus
      • Tietojen validointi
      • Tietokannanhallinta
    • Aiheeseen liittyvät julkaisut:
      • String Tutorial
      • 50 suosituinta merkkijonokoodausongelmaa haastatteluissa
      • Harjoittele ongelmia merkkijonolla

    3. Linkitetyt luettelot

    A linkitetty lista on lineaarinen tietorakenne, joka tallentaa tiedot solmuihin, jotka on yhdistetty osoittimilla. Toisin kuin taulukot, linkitettyjä luetteloita ei tallenneta vierekkäisiin muistipaikkoihin.

    • Linkitetyn listan ominaisuudet:
      • Dynaaminen : Linkitettyjen luetteloiden kokoa voidaan helposti muuttaa lisäämällä tai poistamalla solmuja.
      • Ei vierekkäinen : Solmut on tallennettu satunnaisiin muistipaikkoihin ja yhdistetty osoittimilla.
      • Jaksottainen pääsy : Solmuihin pääsee vain peräkkäin alkaen luettelon päästä.
    • Toiminnot linkitetyssä luettelossa:
      • Luominen : Uuden linkitetyn luettelon luominen tai uuden solmun lisääminen olemassa olevaan luetteloon.
      • Läpikulku : Toistaa luetteloa ja käyttää jokaista solmua.
      • Lisäys : Uuden solmun lisääminen tiettyyn kohtaan luettelossa.
      • Poistaminen : Solmun poistaminen luettelosta.
      • Hae : Tietyn arvon omaavan solmun etsiminen luettelosta.
    • Linkitettyjen luetteloiden tyypit :
      • Yksittäin linkitetty luettelo : Jokainen solmu osoittaa luettelon seuraavaan solmuun.
      • Kaksoislinkitetty lista : Jokainen solmu osoittaa sekä luettelon seuraavaan että edelliseen solmuun.
      • Pyöreä linkitetty luettelo : Viimeinen solmu osoittaa takaisin ensimmäiseen solmuun muodostaen pyöreän silmukan.
    • Linked List -sovellukset :
      • Linkitettyjä luetteloita käytetään useissa sovelluksissa, mukaan lukien:
      • Jonojen ja pinojen toteutus
      • Esittää kaavioita ja puita
      • Tilattujen tietojen ylläpito
      • Muistin hallinta
    • Liittyvät aiheet:
      • Linked List Tutorial
      • 50 suosituinta ongelmaa haastattelujen linkitetyssä luettelossa
      • Harjoittele ongelmia linkitetyissä listoissa

    4. Matriisi/ruudukko

    A matriisi on kaksiulotteinen joukko elementtejä, jotka on järjestetty riveihin ja sarakkeisiin. Se esitetään suorakaiteen muotoisena ruudukkona, jossa jokainen elementti on rivin ja sarakkeen leikkauskohdassa.

    • Keskeiset käsitteet:
      • Rivit : Matriisin elementtien vaakasuuntaiset rivit.
      • Sarakkeet : Matriisin elementtien pystysuorat viivat.
      • Mitat : Matriisin rivien ja sarakkeiden määrä (esim. 3×4-matriisissa on 3 riviä ja 4 saraketta).
      • Elementti Pääsy : Elementtejä voidaan käyttää rivi- ja sarakeindekseillä (esim. M[2][3] viittaa rivin 2 sarakkeen 3 elementtiin).
    • Matrix/Gridin sovellukset :
      • Kuvankäsittely
      • Tietojen analysointi
      • Optimointiongelmia
    • Aiheeseen liittyvät julkaisut:
      • Matrix/Grid Tutorial
      • 50 parasta haastatteluongelmaa Matrixissa/Gridissä
      • Harjoittele ongelmia Matrixissa/Gridissä

    5. Pino

    Pino on lineaarinen tietorakenne, joka noudattaa tiettyä järjestystä, jossa toiminnot suoritetaan. Järjestys voi olla LIFO (viimeinen sisään ensimmäinen ulos) tai FILO (First In Last Out) . LIFO tarkoittaa, että elementti, joka lisätään viimeisenä, tulee ulos ensin ja RIVI tarkoittaa, että ensimmäisenä lisätty elementti tulee ulos viimeisenä.

    • Toiminta pinossa :
      • Työntää : Lisää elementin pinon yläosaan
      • Pop : Poistaa ja palauttaa elementin pinon yläosassa
      • Kurkistaa : Palauttaa pinon yläosassa olevan elementin poistamatta sitä
      • Koko : Palauttaa pinon elementtien määrän
      • On tyhjä : Tarkistaa, onko pino tyhjä
    • Stackin sovellukset :
      • Toimintokutsut
      • Ilmaisun arviointi
      • Perääntyminen
      • Kumoa/toista toiminnot
    • Aiheeseen liittyviä aiheita Stackissa:
      • Pino opetusohjelma
      • 50 parasta haastatteluongelmaa pinossa
      • Harjoittele ongelmia Stackissa

    6. Jonottaa

    A Jonottaa Tietorakenne on tietojenkäsittelytieteen peruskäsite, jota käytetään tietojen tallentamiseen ja hallintaan tietyssä järjestyksessä. Se noudattaa periaatetta Ensimmäinen sisällä ensimmäinen ulkona ( FIFO ), jossa ensimmäinen jonoon lisätty elementti on ensimmäinen, joka poistetaan

    • Toiminta jonossa :
      • Jono : Lisää elementin jonon takaosaan
      • Asianmukaisesti : Poistaa elementin jonon edestä
      • Kurkistaa : Hakee etuosan irrottamatta sitä
      • On tyhjä : Tarkistaa, onko jono tyhjä
      • On täynnä : Tarkistaa, onko jono täynnä
    • Jonon tyyppi :
      • Pyöreä jono : Viimeinen elementti yhdistää ensimmäiseen elementtiin
      • Kaksipäinen jono (deque) : Toiminnot voidaan suorittaa molemmista päistä
      • Prioriteettijono : Elementit on järjestetty tärkeysjärjestyksen mukaan
    • Jonon sovellukset :
      • Työaikataulu
      • Viestijono
      • Simulaatiomallinnus
      • Tietojen puskurointi
    • Liittyvät aiheet:
      • Jonon opetusohjelma
      • 50 parasta haastattelujonossa olevaa ongelmaa
      • Harjoittele ongelmia jonossa

    7. Pino

    A Pino on täydellinen binääripuutietorakenne, joka täyttää keon ominaisuuden: jokaisen solmun lapsien arvo on pienempi tai yhtä suuri kuin sen oma arvo. Toteuttamiseen käytetään yleensä kasoja prioriteettijonot , jossa pienin (tai suurin) elementti on aina puun juuressa.

    • Kasan toiminta :
      • Lisää : Lisää kekoon uuden elementin säilyttäen samalla keon ominaisuudet.
      • Extract-Max/Extract-Min : Poistaa juurielementin ja järjestää kasan uudelleen.
      • Suurenna/pienennä-näppäin : Päivittää solmun arvon ja järjestää keon uudelleen.
    • Kasan tyypit :
      • Max-Heap : Juurisolmulla on suurin arvo lapsiensa joukossa.
      • Min-Heap : Juurisolmulla on pienin arvo lapsiensa joukossa.
    • Kasan sovellukset :
      • Prioriteettijonot
      • Lajittelu
      • Graafialgoritmit (esim. Dijkstran algoritmi)
    • Aiheeseen liittyvät julkaisut:
      • Keon opetusohjelma
      • 50 suosituinta haastatteluongelmaa Heapissa
      • Harjoittele ongelmia Heapissa

    8. Hash

    Hashing on tekniikka, joka luo kiinteän kokoisen lähdön (hash-arvon) muuttuvan kokoisesta syötteestä käyttämällä matemaattisia kaavoja ns. hash-funktiot . Hashing-menetelmää käytetään määrittämään indeksi tai sijainti kohteen tallentamiseksi tietorakenteeseen, mikä mahdollistaa tehokkaan haun ja lisäämisen.

    • Keskeiset käsitteet:
      • Hash-toiminto : Matemaattinen funktio, joka yhdistää syötteen hajautusarvoon.
      • Hash-taulukko : Tietorakenne, joka tallentaa avain-arvo-pareja, joissa avain on hash-arvo ja arvo on todellinen tieto.
      • Törmäys : Kun kaksi eri avainta tuottavat saman hash-arvon.
    • Hash-funktioiden tyypit :
      • Jakomenetelmä : Jakaa syötteen vakiolla ja käyttää jäännöstä hajautusarvona.
      • Keskiaukio Menetelmä: Nelittää syötteen ja ottaa keskimmäiset numerot hash-arvoksi.
      • Taittomenetelmä : Jakaa syötteen samankokoisiin lohkoihin ja lisää ne yhteen saadakseen hash-arvon.
      • Kertolaskumenetelmä : Kertoo syötteen vakiolla ja ottaa murto-osan tiivistearvona.
    • Törmäyksenratkaisutekniikat :
      • Erillinen ketjutus (avoin tiivistys) : Tallentaa törmäävät elementit linkitettyyn luetteloon vastaavaan hajautusarvoon.
      • Avoin osoitus (suljettu hajautus) : Käyttää erilaisia ​​strategioita löytääkseen vaihtoehtoisen paikan törmäyselementeille hajautustaulukossa.
    • Hashingin sovellukset :
      • Tietojen tehokas tallennus ja haku tietokantoihin ja tiedostojärjestelmiin.
      • Salasanojen ja digitaalisten allekirjoitusten tarkistaminen.
      • Pyyntöjen jakaminen useille palvelimille.
      • Luoda turvallisia hajautusarvoja tietojen eheyden ja todentamisen varmistamiseksi.
    • Aiheeseen liittyvät julkaisut:
      • Hash opetusohjelma
      • Harjoittele hajautusongelmia

    9. Puu

    A puu on epälineaarinen hierarkkinen tietorakenne, joka koostuu reunoilla yhdistetyistä solmuista, joiden yläsolmu on juuri ja solmuissa on lapsisolmuja. Sitä käytetään tietojenkäsittelytieteessä tietojen tehokkaaseen järjestämiseen.

    verkkopankkitoiminnan haittoja
    • Puun läpikulku : Puun läpikulkumenetelmiä käytetään puutietorakenteen solmuissa vierailemiseen ja käsittelemiseen. Kolme yleistä läpikulkumenetelmää ovat:
      • Järjestyksessä : Käy vasemmassa alipuussa, nykyisessä solmussa ja sitten oikeassa alipuussa.
      • Ennakkotilaus : Käy nykyisessä solmussa, vasemmassa alipuussa ja sitten oikeassa alipuussa.
      • Jälkitilaus : Käy vasemmassa alipuussa, oikeassa alipuussa ja sitten nykyisessä solmussa.
    • Puiden luokitukset:
      • Luokitukset puut viittaavat puiden ryhmittelyyn tiettyjen ominaisuuksien tai kriteerien perusteella. Tämä voi sisältää puiden luokittelun niiden tasapainokertoimen, solmujen asteen, järjestysominaisuuksien jne. perusteella. Alla on joitakin tärkeitä puun luokituksia.
    Luokittelu Kuvaus

    Tyyppi

    Kuvaus

    Tutkinnon mukaan

    Puut voidaan luokitella kunkin solmun lapsien enimmäismäärän perusteella.

    Binääripuu

    Jokaisella solmulla on enintään kaksi lasta.

    Kolmiosainen puu

    Jokaisella solmulla on enintään kolme lasta.

    N-arinen puu

    Jokaisella solmulla on enintään N lasta.

    Tilaamalla

    Puut voidaan luokitella solmujen ja alipuiden järjestyksen perusteella

    Binäärihakupuu (BST)

    Vasen lapsi

    Pino

    Erikoistunut binääripuu, jolla on kasaominaisuus.

    Balancen mukaan

    Puut voidaan luokitella sen mukaan, kuinka tasapainoisia ne ovat.

    Tasapainoinen puu

    Alipuiden korkeudet eroavat korkeintaan yhdellä. Esimerkkejä ovat AVL-puut ja puna-mustat puut.

    Epätasapainoinen puu

    Alipuiden korkeudet voivat vaihdella merkittävästi, mikä vaikuttaa suorituskykyyn sellaisissa toimissa kuin haku ja lisäys.
    • Puiden sovellukset:
      • Tiedostojärjestelmät
      • Tietokannat
      • XML-dokumentteja
      • Tekoäly
    • Aiheeseen liittyvät julkaisut:
      • Tree opetusohjelma
      • 50 parasta puun koodausongelmaa
      • Harjoittele ongelmia puussa

    10. Kaavio

    A Kaavio on epälineaarinen tietorakenne, joka koostuu äärellisestä joukosta pisteitä (tai solmuja) ja joukosta reunoja, jotka yhdistävät solmuparin.

    operaattorit python-ohjelmoinnissa

    Opi algoritmit

    Kun olet puhdistanut käsitteet Tietorakenteet , nyt on aika aloittaa matkasi Algoritmit . Algoritmit on ryhmitelty useisiin luokkiin luonteen ja käytön perusteella alla olevan kuvan mukaisesti:

    1. Hakualgoritmi

    Hakualgoritmit käytetään tiettyjen tietojen paikantamiseen suuremmasta tietojoukosta. Se auttaa löytämään tavoitearvon läsnäolon tiedoissa. On olemassa erilaisia ​​​​hakualgoritmeja, joista jokaisella on oma lähestymistapansa ja tehokkuutensa.

    • Yleisimmät hakualgoritmit:
      • Lineaarinen haku : Iteratiivinen haku yhdestä päästä toiseen.
      • Binäärihaku : Hae ja hallitse -haku järjestetyssä taulukossa, joka puolittaa hakutilan jokaisessa iteraatiossa.
      • Kolminkertainen haku : Jaa ja hallitse -haku järjestetyssä taulukossa, jakaen hakutilan kolmeen osaan kussakin iteraatiossa.
    • Muut hakualgoritmit:
      • Jump Search
      • Interpolaatiohaku
      • Eksponentiaalinen haku
    • Liittyvät aiheet:
      • Harjoittele hakualgoritmin ongelmia

    2. Lajittelualgoritmi

    Lajittelualgoritmit käytetään luettelon elementtien järjestämiseen tiettyyn järjestykseen, kuten numeeriseen tai aakkosjärjestykseen. Se järjestää kohteet järjestelmällisesti, mikä helpottaa tiettyjen elementtien etsimistä ja käyttöä.

    Lajittelualgoritmeja on monia erilaisia. Joitakin laajalti käytettyjä algoritmeja ovat:

    Lajittelualgoritmi Kuvaus
    Kuplalajittelu Vertailee iteratiivisesti vierekkäisiä elementtejä ja vaihtaa ne, jos ne ovat epäkunnossa. Suurin elementti kuplii luettelon loppuun jokaisella läpikäynnillä.
    Valinta Lajittele Etsii luettelon lajittelemattomasta osasta vähimmäiselementin ja vaihtaa sen ensimmäisen elementin kanssa. Toistaa tätä prosessia, kunnes koko luettelo on lajiteltu.
    Lisäys Lajittele Rakentaa lajiteltua luetteloa elementti kerrallaan lisäämällä kunkin lajittelemattoman elementin oikeaan paikkaan lajiteltuun osuuteen.
    Nopea lajittelu Jaa ja hallitse -algoritmi, joka valitsee pivot-elementin, jakaa luettelon kahdeksi aliluetteloksi pivotin perusteella ja soveltaa rekursiivisesti samaa prosessia aliluetteloihin.
    Yhdistä lajittelu Toinen jakaa ja hallitse -algoritmi, joka jakaa luettelon rekursiivisesti pienempiin aliluetteloihin, lajittelee ne ja yhdistää ne sitten takaisin yhteen, jotta saadaan lajiteltu luettelo.

    Liittyvät aiheet:

    • Lajittelualgoritmin opetusohjelma
    • Parhaat haastattelukysymykset ja -ongelmat
    • Harjoittele ongelmia lajittelualgoritmissa

    3. Jaa ja hallitse -algoritmi

    hajota ja hallitse Algoritmit noudattavat rekursiivista strategiaa ongelmien ratkaisemiseksi jakamalla ne pienempiin osaongelmiin, ratkaisemalla nämä osaongelmat ja yhdistämällä ratkaisut lopullisen ratkaisun saamiseksi.

    Askeleet:

    1. Jakaa : Jaa ongelma pienempiin, itsenäisiin aliongelmiin.
    2. Valloittaa : Ratkaise rekursiivisesti jokainen alitehtävä.
    3. Yhdistää : Yhdistä osatehtävien ratkaisut lopullisen ratkaisun saamiseksi.

    Esimerkkejä:

    • Yhdistä lajittelu: Jakaa taulukon kahteen puolikkaaseen, lajittelee molemmat puolikkaat rekursiivisesti ja yhdistää lajitellut puolikkaat.
    • Pikalajittelu: Valitsee pivot-elementin, jakaa taulukon kahteen alitaulukkoon pivotin perusteella ja lajittelee rekursiivisesti jokaisen alitaulukon.
    • Binäärihaku: Jakaa hakutilan kahtia toistuvasti, kunnes kohdeelementti löytyy tai hakutila on käytetty loppuun.

    Aiheeseen liittyvät artikkelit:

    • Divide and Conquer -opetusohjelma
    • Harjoittele Divide and Conquer -algoritmin ongelmia

    4. Ahneet algoritmit

    Kuten nimestä voi päätellä, tämä algoritmi rakentaa ratkaisun pala kerrallaan ja valitsee seuraavan kappaleen, joka tuottaa ilmeisimmän ja välittömän hyödyn, eli mikä on optimaalisin valinta sillä hetkellä. Joten ongelmat, joissa paikallisesti optimaalisen valitseminen johtaa myös globaaleihin ratkaisuihin, sopivat parhaiten Greedylle.

    Joitakin ahneiden algoritmien tärkeitä ongelmia ovat:

    Algoritmi Kuvaus
    Murtoreppu Selvitä reppuun sijoitettavien tavaroiden enimmäisarvo, mikä mahdollistaa esineiden murto-osan sisällyttämisen.
    Dijkstran algoritmi Löytää lyhimmän polun lähdepisteestä kaikkiin muihin painotetun graafin kärkikohtiin.
    Kruskalin algoritmi Löytää painotetun graafin pienimmän virittävän puun.
    Huffman koodaus Luo optimaalisen etuliitekoodin symbolijoukolle minimoimalla koodauksen kokonaispituuden.

    Aiheeseen liittyvät artikkelit:

    • Greedy Algorithm Tutorial
    • Harjoittele ongelmia Greedy-algoritmissa

    5. Rekursio

    Rekursio on ohjelmointitekniikka, jossa funktio kutsuu itseään oman määritelmänsä puitteissa. Sitä käytetään yleensä ratkaisemaan ongelmia, jotka voidaan jakaa saman ongelman pienempiin esiintymiin. Esimerkiksi: Hanoin tornit (TOH) , Factorial Laskenta ja Fibonaccin sekvenssi jne.

    Askeleet :

    • Perustapaus : Määritä ehto, joka pysäyttää rekursiiviset puhelut ja tarjoaa ratkaisun.
    • Rekursiivinen tapaus : Määritä vaiheet ongelman hajottamiseksi pienempiin tapauksiin ja rekursiivisten puhelujen soittamiseen.
    • Palata : Palauta ratkaisu rekursiivisista kutsuista ja yhdistä ne alkuperäisen ongelman ratkaisemiseksi.

    Se, mikä tekee Rekursiosta yhden käytetyimmistä algoritmeista, on se, että se muodostaa perustan monille muille algoritmeille, kuten esim. Puiden läpikäymiset , Kaavion läpikäymiset , Haja ja hallitse -algoritmit ja Paluualgoritmit .

    Liittyvät aiheet:

    6. Peruutusalgoritmi

    Kuten aiemmin mainittiin, Perääntyminen Algoritmi on johdettu Recursion-algoritmista, jossa on mahdollisuus palata, jos rekursiivinen ratkaisu epäonnistuu, eli jos ratkaisu epäonnistuu, ohjelma jäljittää siihen hetkeen, jolloin se epäonnistui, ja rakentaa toisen ratkaisun. Joten periaatteessa se kokeilee kaikkia mahdollisia ratkaisuja ja löytää oikean.

    Joitakin tärkeitä ja yleisimpiä paluualgoritmien ongelmia, jotka sinun on ratkaistava ennen kuin jatkat eteenpäin, ovat:

    Ongelma Kuvaus
    Knightin kiertueen ongelma Ritarin liikesarjan löytäminen shakkilaudalta siten, että se vierailee jokaisella ruudulla täsmälleen kerran.
    Rotta sokkelossa Löytää polku lähtöpaikasta uloskäyntiin sokkelossa, jossa esteet esitetään seininä.
    N-Queen ongelma N:n kuningattaren asettaminen N×N-shakkilaudalle siten, että kaksi kuningatarta ei hyökkää toisiaan vastaan.
    Osajoukon summa -ongelma Sen määrittäminen, onko annetusta joukosta olemassa osajoukko tietyllä summalla.
    Sudoku 9 × 9 -ruudukon pulmapelin ratkaiseminen numeroilla 1 - 9 siten, että jokainen rivi, sarake ja 3 × 3 -aliruudukko sisältää kaikki numerot ilman toistoa.

    Aiheeseen liittyvä artikkeli:

    • Backtracking opetusohjelma
    • Harjoittele Backtracking-algoritmin ongelmia

    7. Dynaaminen ohjelmointi

    Dynaaminen ohjelmointi on matematiikassa ja tietojenkäsittelytieteessä käytetty menetelmä monimutkaisten ongelmien ratkaisemiseksi jakamalla ne yksinkertaisempiin osaongelmiin. Ratkaisemalla jokainen aliongelma vain kerran ja tallentamalla tulokset, se välttää redundantteja laskelmia, mikä johtaa tehokkaampiin ratkaisuihin monenlaisiin ongelmiin.

    Keskeiset käsitteet:

    • Optimaalinen alusrakenne : Optimaalinen ratkaisu ongelmaan voidaan rakentaa optimaalisista ratkaisuista sen osaongelmiin.
    • Päällekkäiset aliongelmat : Aliongelmat toistuvat usein suuremmassa ongelmassa, mikä johtaa redundanttisiin laskelmiin.
    • Memoisointi / Taulukko : Aliongelmien ratkaisujen tallentaminen uudelleenlaskennan välttämiseksi.

    Joitakin tärkeitä ja yleisimpiä dynaamisten ohjelmointialgoritmien ongelmia, jotka sinun on ratkaistava ennen kuin jatkat eteenpäin, ovat:

    Ongelma Kuvaus
    Fibonaccin sekvenssi Fibonacci-lukujen luominen dynaamisen ohjelmoinnin avulla redundanttien laskelmien välttämiseksi.
    Pisin yhteinen jakso Pisin kahdelle sekvenssille yhteinen osasekvenssi.
    Pisin kasvava jakso Tietyn sekvenssin pisimmän osajonon löytäminen, jossa elementit lajitellaan kasvavassa järjestyksessä.
    0/1 Reppu-ongelma Maksimiarvon määrittäminen, joka voidaan saada valitsemalla kohteita, joilla on tietyt painot ja arvot, mutta ei ylitetä määritettyä painorajaa.
    Tangon leikkaus ongelma Voiton maksimoiminen leikkaamalla tietynpituinen sauva paloiksi ja myymällä ne annettujen hintojen mukaan.
    Kolikon vaihtoongelma Sen määrittäminen, kuinka monta tapaa tehdä muutos tietylle summalle käyttämällä tiettyä kolikoiden nimellisarvoa.
    Muokkaa etäisyyttä Löytää vähimmäismäärä operaatioita (lisäys, poisto, korvaaminen), joka tarvitaan merkkijonon muuntamiseen toiseksi.
    Osajoukon summa -ongelma Sen määrittäminen, onko tietyllä joukolla olemassa osajoukko tietyllä summalla.
    Pisin palindrominen alajakso Tietyn sekvenssin pisimmän osasekvenssin löytäminen, joka on palindromi.
    Suurin Subarray Sum Vierekkäisen alitaulukon löytäminen, jonka summa on suurin tietyssä yksiulotteisessa taulukossa.
    Osion yhtä suuri osajoukon summa Sen määrittäminen, onko mahdollista jakaa annettu joukko kahdeksi osajoukoksi yhtä suurella summalla.
    Minimikustannuspolku Minimikustannuspolun etsiminen tietyn ruudukon vasemmasta yläkulmasta oikeaan alakulmaan.
    Suurin tuote-aliryhmä Vierekkäisen alitaulukon löytäminen, jossa on suurin tulo tietyssä yksiulotteisessa taulukossa.

    Aiheeseen liittyvät artikkelit:

    • Taulukko vs muistiinpano
    • Kuinka ratkaista dynaamisen ohjelmoinnin ongelma?
    • Dynaamisen ohjelmoinnin opetusohjelma
    • 50 suosituinta dynaamisen ohjelmoinnin koodausongelmaa haastatteluihin
    • Harjoittele ongelmia dynaamisen ohjelmoinnin algoritmissa

    8. Graafialgoritmit :

    Graafialgoritmit Tietorakenteet ja -algoritmit (DSA) ovat joukko tekniikoita ja menetelmiä, joita käytetään graafisiin liittyvien ongelmien ratkaisemiseen, jotka muodostavat kokoelman solmuja ja reunoja. Nämä algoritmit on suunniteltu suorittamaan erilaisia ​​toimintoja kaavioille, kuten etsiminen, kulkeminen, lyhimmän polun löytäminen , ja määrittävä liitettävyyttä . Ne ovat välttämättömiä monien todellisten ongelmien ratkaisemisessa, mukaan lukien verkon reititys, sosiaalisen verkoston analyysi ja resurssien allokointi.

    Aihe

    Aiheen kuvaus

    		 Algoritmi Algoritmin kuvaus
    Kaavion läpikulku

    Tekniikat graafin kaikissa pisteissä vierailemiseen.

    		 Depth-First Search (DFS) Tutki kutakin haaraa mahdollisimman pitkälle ennen perääntymistä.
    Breadth-First Search (BFS) Tutkii naapuripisteitä ennen siirtymistä seuraavalle tasolle.

    Vähimmäisylimääräiset puut

    Vähimmäisvirittävät puut ovat pienimpiä puita, jotka yhdistävät kaikki graafin solmut muodostamatta syklejä, mikä saavutetaan lisäämällä lyhyimmät mahdolliset reunat.

    Kruskalin algoritmi

    Se löytää vähintään virittävän puun yhdistetylle painotetulle graafille. Se lisää pienimmän painoreunan, joka ei muodosta sykliä.

    Primin algoritmi

    Se löytää myös vähimmäisvirittävän puun yhdistetylle painotetulle graafille. Se lisää pienimmän painoreunan, joka yhdistää kaksi puuta.

    Estä mainokset YouTubessa Android
    Topologinen lajittelu

    Topologinen lajittelu on suunnatun asyklisen graafin (DAG) kärkien lineaarista järjestystä siten, että jokaisessa suunnatussa reunassa kärjestä u kärkeen v, u tulee ennen v:tä järjestyksessä.

    		 Kahnin algoritmi Kahnin algoritmi löytää suunnatun asyklisen graafin (DAG) topologisen järjestyksen.
    DFS-pohjainen algoritmi DFS-pohjainen algoritmi käyttää Depth-First-hakua topologisen lajittelun suorittamiseen suunnatussa asyklisessä graafissa (DAG).

    Lyhin polku

    Lyhyin polku graafissa on graafin kahden kärjen välinen polku, jonka reunoilla on pienin painojen summa verrattuna kaikkiin muihin samojen kahden kärjen välisiin polkuihin.

    Dijkstran algoritmi

    Ahne algoritmi löytää lyhimmän polun kaikkien solmujen välillä O(E * V logV) ajassa.

    Floyd-Warshall-algoritmi

    Löytää lyhimmän polun kaikkien solmuparien välillä O(V^3)-ajassa.

    Bellman Ford -algoritmi

    Löytää lyhimmän polun yhdestä lähteestä O(V * E) -ajassa.

    Johnsonin algoritmi

    Löytää lyhyimmät polut kaikkien kärkiparien välillä O(V^2 logV + V * E) ajassa.

    Vahvasti yhdistetyt komponentit

    Suunnatun graafin vahvasti kytketty komponentti (SCC) on maksimi pistejoukko siten, että jokaisesta joukon kärjestä on polku jokaiseen joukon toiseen kärkeen.

    Kosarajun algoritmi

    Kosaraju's Algorithm on kaksivaiheinen algoritmi, joka löytää tehokkaasti suunnatun graafin vahvasti toisiinsa liittyvät komponentit (SCC).

    Tarjan’s Algorithm

    Tarjan's Algorithm on toinen tehokas algoritmi SCC:iden löytämiseen suunnatusta graafista

    Liittyvät aiheet:

    • Kaavion opetusohjelma
    • 50 suosituinta kaavion koodausongelmaa haastatteluissa
    • Graafialgoritmien harjoitustehtävä

    9 . Kuvion haku

    Kuvion haku on DSA:n perustekniikka, jota käytetään tietyn kuvion esiintymien etsimiseen annetusta tekstistä.

    Alla on joitain vakiomallin hakualgoritmeja:

    Algoritmi Kuvaus Aika monimutkaisuus
    Raaka voima Se vertaa kuviota jokaiseen tekstin osamerkkijonoon O(mn)
    Knuth-Morris-Pratt Se käyttää ennalta laskettua vikatoimintoa tarpeettomien vertailujen ohittamiseen O(m + n)
    Boyer-Moore Se vertaa kuviota oikealta vasemmalle ohittaen merkit viimeisimmän yhteensopimattomuuden perusteella O(mn)
    Rabin-Karp Se käyttää tiivistystä mahdollisten osumien nopeaan tarkistamiseen O(m + n)

    Liittyvät aiheet:

    • Kuviohaun opetusohjelma
    • Harjoitusongelma päällä Kuvion haku

    10 . Matemaattiset algoritmit

    Matemaattiset algoritmit ovat luokka algoritmeja, jotka ratkaisevat matemaattisiin käsitteisiin liittyviä ongelmia. Niitä käytetään laajasti eri aloilla, mukaan lukien tietokonegrafiikka, numeerinen analyysi, optimointi ja kryptografia.

    Algoritmi Kuvaus
    GCD ja LCM Etsi kahden luvun suurin yhteinen jakaja ja pienin yhteinen kerrannainen.
    Alkutekijähajotelma Jaa luku sen alkutekijöiksi.
    Fibonaccin numerot Luo Fibonacci-sekvenssi, jossa jokainen luku on kahden edellisen summa.
    Katalonian numerot Laske kelvollisten lausekkeiden määrä tietyllä määrällä sulkupareja.
    Modulaarinen aritmetiikka Suorita aritmeettisia operaatioita luvuille moduloi annettua arvoa.
    Euler Totient -funktio Laske tiettyä määrää pienempien positiivisten kokonaislukujen määrä, jotka ovat suhteellisen alkulukuja sille.
    nCr-laskelmat Laske binomikerroin, joka edustaa kuinka monta tapaa valita r elementtiä n elementin joukosta.
    Alkuluvut ja primaalisuustestit Selvitä, onko annettu luku alkuluku ja löydä alkuluvut tehokkaasti.
    Seula-algoritmit Etsi kaikki alkuluvut tiettyyn rajaan asti.

    Liittyvät aiheet:

    • Matemaattisen algoritmin harjoitustehtävä

    11. Geometriset algoritmit

    Geometriset algoritmit ovat luokka algoritmeja, jotka ratkaisevat geometriaan liittyviä ongelmia. Geometriset algoritmit ovat välttämättömiä useiden tietojenkäsittelytieteen ongelmien ratkaisemiseksi, kuten:

    Algoritmi Kuvaus
    Kupera runko Etsii pienimmän kuperan monikulmion, joka sisältää joukon pisteitä.
    Lähin pistepari Löytää kaksi pistettä joukosta, jotka ovat lähimpänä toisiaan.
    Linjojen leikkaus Määrittää, leikkaavatko kaksi suoraa, ja jos on, löytää leikkauspisteen.
    Piste polygonissa Määrittää, onko tietty piste monikulmion sisällä vai ulkopuolella.

    Liittyvät aiheet:

    • Geometristen algoritmien harjoitustehtävä

    12. Bittikohtaiset algoritmit

    Bittikohtaiset algoritmit ovat algoritmeja, jotka toimivat yksittäisillä numerobitteillä. Nämä algoritmit manipuloivat numeroiden binääriesitystä suorittaakseen tehtäviä, kuten bittimanipulaatiota, bittikohtaisia ​​loogisia operaatioita (AND, OR, XOR), vaihtavat bitit , ja asetusta tai tiettyjen bittien poistaminen numeron sisällä. Bittikohtaisia ​​algoritmeja käytetään yleisesti matalan tason ohjelmointi-, salaus- ja optimointitehtävät joissa tarvitaan yksittäisten bittien tehokasta käsittelyä.

    Aihe Kuvaus
    Bitin vaihto Siirtää bittejä vasemmalle tai oikealle tietyn määrän paikkoja.
    Vaihto vasemmalle (<<) Siirtää bittejä vasemmalle kertoen luvun tehokkaasti kahdella.
    Vaihto oikealle (>>) Siirtää bittejä oikealle jakaen luvun tehokkaasti kahdella.
    Pura bittejä Maskien käyttäminen tiettyjen bittien poimimiseen kokonaisluvusta.
    Asetusbitit Maskien käyttäminen asettaaksesi tietyt bitit 1:ksi kokonaisluvussa.
    Bittien tyhjennys Maskien käyttäminen asettaaksesi tietyt bitit nollaksi kokonaisluvussa.
    Bittien vaihto XOR:n (^) käyttö vaihtaaksesi tiettyjä bittejä kokonaisluvussa.
    Bittien laskenta Laskee asetettujen bittien lukumäärän (1 s) kokonaisluvussa.

    Liittyvät aiheet:

    • Bittikohtaisten algoritmien opetusohjelma
    • Harjoittele ongelmaa bittikohtaisissa algoritmeissa

    13. Satunnaistetut algoritmit

    Satunnaistetut algoritmit ovat algoritmeja, jotka käyttävät satunnaisuutta ongelmien ratkaisemiseen. He käyttävät satunnaista panosta saavuttaakseen tavoitteensa, mikä johtaa usein yksinkertaisempiin tai tehokkaampiin ratkaisuihin.

    Satunnaistettujen algoritmien tyypit:

    • Las Vegas : Antaa aina oikean tuloksen, mutta ajoaika on satunnainen.
    • Monte Carlo : Saattaa tuottaa väärän tuloksen pienellä todennäköisyydellä, mutta ajoaika on yleensä nopeampi.

    Tärkeitä algoritmeja, jotka käyttävät satunnaisalgoritmeja:

    Algoritmi Kuvaus
    QuickSort Satunnaistettu lajittelualgoritmi, jonka keskimääräinen aikakompleksisuus on O(n log n).
    Ohita lista Satunnaistettu tietorakenne, joka tarjoaa nopeat haku- ja lisäystoiminnot.
    Bloom-suodatin Todennäköisyyspohjainen tietorakenne tehokkaaseen joukon jäsenyystestaukseen.

    14. Haara ja sidottu algoritmi

    The Haara ja sidottu algoritmi on menetelmä, jota käytetään kombinatorisissa optimointitehtävissä parhaan ratkaisun systemaattiseen etsimiseen. Se toimii jakamalla ongelman pienempiin osaongelmiin tai haaroihin ja poistamalla sitten tietyt haarat optimaalisen ratkaisun rajojen perusteella. Tätä prosessia jatketaan, kunnes paras ratkaisu löytyy tai kaikki haarat on tutkittu.

    Haara- ja sidotusalgoritmin vakioongelmat:

    Ainutlaatuinen ongelma Kuvaus
    0/1 Reppu käyttäen Branch and Boundia Haaran ja sidotun lähestymistavan toteutustiedot 0/1-reppu-ongelman ratkaisemiseksi.
    0/1 Reppu käyttäen vähiten kustannuksia olevaa haaraa ja sidottua 0/1-reppu-ongelman ratkaiseminen edullisimmalla haara- ja sidontatekniikalla.
    8-pulma-ongelma Branch and Boundin käytössä Haarasovellus ja sidottu ratkaisemaan 8-pulmaongelma, suosittu liukuva pulmapeli.
    N Queen-ongelma Branch and Boundin käytössä Käyttää haaraa ja löytää ratkaisuja N Queensin ongelmaan, klassiseen shakkitehtävään.

    Liittyvät aiheet:

    • Branch and Bound Algorithm Tutorial

    Opi monimutkaisuuksista

    Data Structures and Algorithms (DSA) -sovelluksessa päätavoitteena on ratkaista ongelmia tehokkaasti ja tehokkaasti. Ohjelman tehokkuuden määrittämiseksi tarkastelemme kahta tyyppiä monimutkaisuutta:

    1. Aika monimutkaisuus : Tämä kertoo meille, kuinka kauan koodimme suorittaminen kestää.
    2. Avaruuden monimutkaisuus : Tämä kertoo kuinka paljon muistia koodimme käyttää.

    Asymptoottinen merkintä :

    Algoritmien tehokkuuksien vertaamiseen käytämme asymptoottista merkintää, matemaattista työkalua, joka arvioi aika perustuen syöttökoko ilman koodia. Se keskittyy ohjelman perustoimintojen määrään.

    Merkintä Kuvaus
    Big-O (Ο) Kuvaa pahimman mahdollisen skenaarion ja tarjoaa algoritmin ylemmän aikarajan.
    Omega (Ω) Kuvaa parhaan mahdollisen skenaarion ja tarjoaa algoritmin alemman aikarajan.
    Theta (θ) Edustaa algoritmin algoritmin keskimääräistä monimutkaisuutta.

    Yleisimmin käytetty koodianalyysin merkintätapa on Iso O-merkintä , joka tarjoaa ylärajan käyntiajalle tai muistin käytölle tulokoon suhteen.

    Liittyvät aiheet:

    Harjoittele ongelmahuijauslehtiä:

    Kuroidut luettelot ongelmista alla olevista artikkeleista:

    • DSA Roadmap, Sandeep Jain
    • SDE SHEET – Täydellinen opas SDE:n valmisteluun
    • techcodeview.com Master Sheet – Luettelo kaikista huijausarkeista