logo

TechCodeview

Lær datastrukturer og algoritmer | DSA veiledning

Datastrukturer og algoritmer (DSA) referere til studiet av metoder for organisering og lagring av data og utforming av prosedyrer (algoritmer) for å løse problemer, som opererer på disse datastrukturene. DSA er en av de viktigste ferdighetene som enhver informatikkstudent må ha. Det er ofte sett at folk med god kunnskap om disse teknologiene er bedre programmerere enn andre og dermed knekker intervjuene til nesten alle teknologigiganter. Dette DSA-opplæring har som mål å hjelpe deg å lære datastrukturer og algoritmer (DSA) raskt og enkelt.



Innholdsfortegnelse

  • Lær algoritmer
  • Lær om kompleksiteter
  • Praksis Problem Cheat Sheets

    • DSA Full Form

    Begrepet DSA står for Datastrukturer og algoritmer , i sammenheng med informatikk.

    Hva er DSA?

    Datastrukturer og algoritmer (DSA) referere til studiet av metoder for organisering og lagring av data og utforming av prosedyrer (algoritmer) for å løse problemer, som opererer på disse datastrukturene.



    Hvordan lære DSA?

    Det første og fremste er å dele den totale prosedyren i små biter som må gjøres sekvensielt. Den komplette prosessen for å lære DSA fra bunnen av kan deles inn i 5 deler:

    1. Lær minst ett programmeringsspråk (vi overlater dette til ditt valg.)
    2. Lær datastrukturer
    3. Lær algoritmer
    4. Lær om kompleksiteten i tid og rom
    5. Praksisproblemer på DSA
    Hvordan lære DSA?

    Hvordan lære DSA?

    I håp om at du har lært et programmeringsspråk du ønsker, la oss gå videre med neste trinn for å lære DSA i denne DSA-opplæringen.



    Her kommer det viktigste og mest etterlengtede stadiet av veikartet for å lære datastruktur og algoritme – stadiet der du begynner å lære om DSA. Temaet DSA består av to deler:

    • Datastrukturer
    • Algoritmer

    Selv om de er to forskjellige ting, er de svært beslektet, og det er veldig viktig å følge rett spor for å lære dem mest effektivt. Hvis du er forvirret om hvilken du skal lære først, anbefaler vi deg å gå gjennom vår detaljerte analyse om emnet: Her har vi fulgt flyten med å lære en datastruktur og deretter de mest relaterte og viktige algoritmene som brukes av den datastrukturen.

    Lær datastrukturer

    Datastrukturer er viktige komponenter som hjelper til med å organisere og lagre data effektivt i datamaskinens minne. De gir en måte å administrere og manipulere data effektivt, og muliggjør raskere tilgang, innsetting og sletting. Vanlige datastrukturer inkluderer matriser, koblede lister, stabler, køer, trær og grafer , som hver tjener spesifikke formål basert på kravene til det aktuelle problemet. Å forstå datastrukturer er grunnleggende for å designe effektive algoritmer og optimalisere programvareytelsen.

    Array er en lineær datastruktur som lagrer en samling av elementer av samme datatype. Elementer tildeles sammenhengende minne, noe som gir konstant-tidstilgang. Hvert element har et unikt indeksnummer.

    • Operasjoner på Array:
      • Traversering : Iterering gjennom elementene i en matrise.
      • Innsetting : Legge til et element til matrisen ved en bestemt indeks.
      • Sletting : Fjerne et element fra matrisen ved en bestemt indeks.
      • Søker : Finne et element i matrisen etter verdien eller indeksen.
    • Typer av matriser :
      • Endimensjonal matrise : En enkel matrise med en enkelt dimensjon.
      • Flerdimensjonal matrise : En matrise med flere dimensjoner, for eksempel en matrise.
    • Applikasjoner av Array :
      • Lagre data på en sekvensiell måte
      • Implementering av køer, stabler og andre datastrukturer
      • Representerer matriser og tabeller
    • Relaterte emner om Array:
      • Veiledning for matriser
      • Topp 50 array-kodingsproblemer for intervjuer
      • Øv problemer på Arrays

    2. String

    EN streng er en sekvens av tegn, vanligvis brukt til å representere tekst. Det regnes som en datatype som gjør det mulig å manipulere og behandle tekstdata i dataprogrammer.

    • Operasjoner på String :
      • Sammenkobling : Sammenføyning av to strenger.
      • Sammenligning : Sammenligning av to strenger leksikografisk.
      • Understreng utdrag : Trekker ut en delstreng fra en streng.
      • Søk : Søker etter en understreng i en streng.
      • Modifikasjon : Endre eller erstatte tegn i en streng.
    • Applikasjoner av String :
      • Tekstbehandling
      • Mønstermatching
      • Datavalidering
      • Database ledelse
    • Relaterte innlegg:
      • Strengeveiledning
      • Topp 50 strengkodingsproblemer for intervjuer
      • Øv problemer på streng

    3. Koblede lister

    EN koblet liste er en lineær datastruktur som lagrer data i noder, som er forbundet med pekere. I motsetning til matriser, lagres ikke koblede lister i sammenhengende minneplasseringer.

    • Kjennetegn på koblet liste:
      • Dynamisk : Koblede lister kan enkelt endres ved å legge til eller fjerne noder.
      • Ikke sammenhengende : Noder er lagret i tilfeldige minneplasseringer og koblet sammen med pekere.
      • Sekvensiell tilgang : Noder kan bare nås sekvensielt, fra toppen av listen.
    • Operasjoner på koblet liste:
      • Opprettelse : Opprette en ny koblet liste eller legge til en ny node til en eksisterende liste.
      • Traversering : Itererer gjennom listen og får tilgang til hver node.
      • Innsetting : Legger til en ny node på en bestemt posisjon i listen.
      • Sletting : Fjerner en node fra listen.
      • Søk : Finne en node med en bestemt verdi i listen.
    • Typer koblet liste :
      • Enkeltlenket liste : Hver node peker til neste node i listen.
      • Dobbeltkoblet liste : Hver node peker til både neste og forrige node i listen.
      • Sirkulær lenket liste : Den siste noden peker tilbake til den første noden, og danner en sirkulær sløyfe.
    • Applikasjoner av koblet liste :
      • Koblede lister brukes i ulike applikasjoner, inkludert:
      • Implementering av køer og stabler
      • Representerer grafer og trær
      • Vedlikeholde bestilte data
      • Minnehåndtering
    • Relaterte temaer:
      • Opplæring i lenket liste
      • Topp 50 problemer på lenket liste for intervjuer
      • Øv problemer på koblede lister

    4. Matrise/Grid

    EN matrise er en todimensjonal rekke elementer, ordnet i rader og kolonner. Det er representert som et rektangulært rutenett, med hvert element i skjæringspunktet mellom en rad og kolonne.

    • Nøkkelkonsepter:
      • Rader : Horisontale linjer av elementer i en matrise.
      • Kolonner : Vertikale linjer av elementer i en matrise.
      • Dimensjoner : Antall rader og kolonner i en matrise (f.eks. en 3×4-matrise har 3 rader og 4 kolonner).
      • Element Adgang : Elementer kan nås ved å bruke rad- og kolonneindekser (f.eks. M[2][3] refererer til elementet i rad 2, kolonne 3).
    • Anvendelser av Matrix/Grid :
      • Bildebehandling
      • Dataanalyse
      • Optimaliseringsproblemer
    • Relaterte innlegg:
      • Veiledning for matrise/rutenett
      • Topp 50 problemer på matrise/rutenett for intervjuer
      • Øv problemer på matrise/rutenett

    5. Stable

    Stable er en lineær datastruktur som følger en bestemt rekkefølge operasjonene utføres i. Rekkefølgen kan være LIFO (sist inn først ut) eller FILO (først inn sist ut) . LIFO innebærer at elementet som settes inn sist, kommer først ut og RAD innebærer at elementet som settes inn først, kommer sist ut.

    • Operasjon på stabel :
      • Trykk : Legger til et element på toppen av stabelen
      • Pop : Fjerner og returnerer elementet på toppen av stabelen
      • Kikk : Returnerer elementet øverst i stabelen uten å fjerne det
      • Størrelse : Returnerer antall elementer i stabelen
      • Er tom : Sjekker om stabelen er tom
    • Applikasjoner av Stack :
      • Funksjonsanrop
      • Uttrykksevaluering
      • Tilbakesporing
      • Angre/gjør om operasjoner
    • Relaterte emner på stabelen:
      • Stabelopplæring
      • Topp 50 problemer på stabel for intervjuer
      • Øv problemer på Stack

    6. Kø

    EN Kø Datastruktur er et grunnleggende konsept innen informatikk som brukes til å lagre og administrere data i en bestemt rekkefølge. Det følger prinsippet om Først inn først ut ( FIFO ), der det første elementet som legges til i køen er det første som fjernes

    • Operasjon på kø :
      • Kø : Legger til et element bak i køen
      • Tilsvarende : Fjerner et element fra forsiden av køen
      • Kikk : Henter frem frontelementet uten å fjerne det
      • Er tom : Sjekker om køen er tom
      • Er full : Sjekker om køen er full
    • Type kø :
      • Sirkulær kø : Siste element kobles til det første elementet
      • Dobbeltkø (deque) : Operasjoner kan utføres fra begge ender
      • Prioritetskø : Elementer er ordnet ut fra prioritet
    • Applikasjoner av kø :
      • Jobbplanlegging
      • Meldingskø
      • Simuleringsmodellering
      • Databuffring
    • Relaterte temaer:
      • Køopplæring
      • Topp 50 problemer i kø for intervjuer
      • Øv problemer på kø

    7. Heap

    EN Heap er en komplett binær tredatastruktur som tilfredsstiller heap-egenskapen: for hver node er verdien av dens barn mindre enn eller lik dens egen verdi. Dynger brukes vanligvis til å implementere prioriterte køer , hvor det minste (eller største) elementet alltid er ved roten av treet.

    • Drift av Heap :
      • Sett inn : Legger til et nytt element til haugen samtidig som haugegenskapene opprettholdes.
      • Ekstraher-Max/Extract-Min : Fjerner rotelementet og omstrukturerer haugen.
      • Øk/minsk-tast : Oppdaterer verdien til en node og omstrukturerer heapen.
    • Typer av hauger :
      • Max-Heap : Rotnoden har den maksimale verdien blant sine barn.
      • Min-haug : Rotnoden har minimumsverdien blant sine barn.
    • Applikasjoner av Heap :
      • Prioriterte køer
      • Sortering
      • Grafalgoritmer (f.eks. Dijkstras algoritme)
    • Relaterte innlegg:
      • Heap Tutorial
      • Topp 50 problemer på Heap for intervjuer
      • Øv problemer på Heap

    8. Hash

    Hashing er en teknikk som genererer en utdata med fast størrelse (hash-verdi) fra en inngang av variabel størrelse ved å bruke matematiske formler kalt hash-funksjoner . Hashing brukes til å bestemme en indeks eller plassering for lagring av et element i en datastruktur, noe som muliggjør effektiv henting og innsetting.

    • Nøkkelkonsepter:
      • Hash funksjon : En matematisk funksjon som tilordner en inngang til en hash-verdi.
      • Hash-tabell : En datastruktur som lagrer nøkkel-verdi-par, der nøkkelen er en hash-verdi og verdien er de faktiske dataene.
      • Kollisjon : Når to forskjellige nøkler produserer samme hashverdi.
    • Typer hash-funksjoner :
      • Divisjonsmetode : Deler inndata med en konstant og bruker resten som hash-verdi.
      • Mid Square Metode: Kvadrerer inndata og tar de midterste sifrene som hash-verdi.
      • Foldemetode : Deler inndata i like store blokker og legger dem sammen for å få hash-verdien.
      • Multiplikasjonsmetode : Multipliserer inndata med en konstant og tar brøkdelen som hashverdi.
    • Teknikker for kollisjonsløsning :
      • Separat kjetting (åpen hashing) : Lagrer kolliderende elementer i en koblet liste med den tilsvarende hash-verdien.
      • Åpen adressering (lukket hashing) : Bruker ulike strategier for å finne en alternativ plassering for kolliderende elementer i hashtabellen.
    • Applikasjoner av hashing :
      • Effektiv lagring og henting av data i databaser og filsystemer.
      • Verifisering av passord og digitale signaturer.
      • Distribuere forespørsler på tvers av flere servere.
      • Generer sikre hashes for dataintegritet og autentisering.
    • Relaterte innlegg:
      • Hash-opplæring
      • Øv problemer på hashing

    9. Tre

    EN tre er en ikke-lineær hierarkisk datastruktur som består av noder forbundet med kanter, med en toppnode kalt roten og noder som har barnenoder. Det brukes i informatikk for å organisere data effektivt.

    hva er størrelsen på skjermen min
    • Traversering av tre : Tregjennomgangsmetoder brukes til å besøke og behandle noder i en tredatastruktur. De tre vanlige traverseringsmetodene er:
      • I rekkefølge : Besøk venstre undertre, gjeldende node, deretter høyre undertre.
      • Forhåndsbestille : Besøk gjeldende node, venstre undertre, deretter høyre undertre.
      • Etterbestilling : Besøk venstre undertre, høyre undertre, deretter gjeldende node.
    • Klassifikasjoner av trær:
      • Klassifikasjoner av Trær refererer til gruppering av trær basert på visse egenskaper eller kriterier. Dette kan innebære å kategorisere trær basert på deres balansefaktor, grad av noder, bestillingsegenskaper osv. Nedenfor er noen viktige klassifiseringer av Tree.
    Klassifisering Beskrivelse

    Type

    Beskrivelse

    Etter grad

    Trær kan klassifiseres basert på det maksimale antallet barn hver node kan ha.

    Binært tre

    Hver node har maksimalt to barn.

    Ternært tre

    Hver node har maksimalt tre barn.

    N-ært tre

    Hver node har maksimalt N barn.

    Ved bestilling

    Trær kan klassifiseres basert på rekkefølgen av noder og undertrær

    Binært søketre (BST)

    Venstre barn

    Heap

    Spesialisert binært tre med haugeiendommen.

    Etter balanse

    Trær kan klassifiseres basert på hvor godt balansert de er.

    Balansert tre

    Høyden på undertrær avviker med høyst én. Eksempler inkluderer AVL-trær og rød-svarte trær.

    ulv vs rev

    Ubalansert tre

    Høyden på undertrær kan variere betydelig, noe som påvirker ytelsen i operasjoner som søk og innsetting.
    • Bruk av trær:
      • Filsystemer
      • Databaser
      • XML-dokumenter
      • Kunstig intelligens
    • Relaterte innlegg:
      • Treopplæring
      • Topp 50 trekodingsproblemer
      • Øv problemer på Tree

    10. Graf

    EN Kurve er en ikke-lineær datastruktur som består av et begrenset sett med toppunkter (eller noder) og et sett med kanter som forbinder et par noder.

    Lær algoritmer

    Når du har ryddet begrepene av Datastrukturer , nå er det på tide å starte reisen gjennom Algoritmer . Basert på type natur og bruk, er algoritmene gruppert sammen i flere kategorier, som vist nedenfor:

    1. Søkealgoritme

    Søkealgoritmer brukes til å lokalisere spesifikke data innenfor et større sett med data. Det hjelper å finne tilstedeværelsen av en målverdi i dataene. Det finnes ulike typer søkealgoritmer, hver med sin egen tilnærming og effektivitet.

    • De vanligste søkealgoritmene:
      • Lineært søk : Iterativt søk fra den ene enden til den andre.
      • Binært søk : Del-og-hersk-søk på en sortert matrise, halver søkeområdet ved hver iterasjon.
      • Ternært søk : Del-og-hersk-søk på en sortert matrise, og deler søkeområdet i tre deler ved hver iterasjon.
    • Andre søkealgoritmer:
      • Hoppsøk
      • Interpolasjonssøk
      • Eksponentielt søk
    • Relaterte temaer:
      • Øv på problemer med søkealgoritmen

    2. Sorteringsalgoritme

    Sorteringsalgoritmer brukes til å ordne elementene i en liste i en bestemt rekkefølge, for eksempel numerisk eller alfabetisk. Den organiserer elementene på en systematisk måte, noe som gjør det lettere å søke etter og få tilgang til spesifikke elementer.

    Det finnes mange forskjellige typer sorteringsalgoritmer. Noen mye brukte algoritmer er:

    Sorteringsalgoritme Beskrivelse
    Boblesortering Iterativt sammenligner tilstøtende elementer og bytter dem hvis de er ute av drift. Det største elementet bobler til slutten av listen med hver pass.
    Utvalgssortering Finner minimumselementet i den usorterte delen av listen og bytter det med det første elementet. Gjentar denne prosessen til hele listen er sortert.
    Innsettingssortering Bygger den sorterte listen ett element om gangen ved å sette inn hvert usorterte element på riktig plassering i den sorterte delen.
    Rask sortering En del-og-hersk-algoritme som velger et pivotelement, deler listen inn i to underlister basert på pivoten, og bruker den samme prosessen rekursivt på underlistene.
    Slå sammen sortering En annen del-og-hersk-algoritme som rekursivt deler listen inn i mindre underlister, sorterer dem og deretter slår dem sammen igjen for å få den sorterte listen.

    Relaterte temaer:

    • Opplæring i sorteringsalgoritme
    • Toppsortering av intervjuspørsmål og -problemer
    • Øv på problemer med sorteringsalgoritme

    3. Divide and Conquer-algoritme

    Splitt og hersk Algoritmer følger en rekursiv strategi for å løse problemer ved å dele dem inn i mindre delproblemer, løse disse delproblemene og kombinere løsningene for å oppnå den endelige løsningen.

    Trinn:

    1. Dele opp : Del opp problemet i mindre, uavhengige delproblemer.
    2. Erobre : Løs hvert delproblem rekursivt.
    3. Kombinere : Slå sammen løsningene til deloppgavene for å få den endelige løsningen.

    Eksempler:

    • Slå sammen sortering: Deler matrisen i to halvdeler, sorterer hver halvdel rekursivt og slår sammen de sorterte halvdelene.
    • Hurtigsortering: Velger et pivotelement, deler opp arrayen i to subarrays basert på pivoten, og sorterer rekursivt hver subarray.
    • Binært søk: Deler søkeområdet i to gjentatte ganger til målelementet er funnet eller søkeområdet er oppbrukt.

    Relaterte artikler:

    • Del og hersk veiledning
    • Øv problemer på Divide And Conquer-algoritmen

    4. Grådige algoritmer

    Som navnet antyder, bygger denne algoritmen opp løsningen ett stykke om gangen og velger det neste stykket som gir den mest åpenbare og umiddelbare fordelen, dvs. som er det mest optimale valget i det øyeblikket. Så problemene der å velge lokalt optimalt også fører til at de globale løsningene passer best for Greedy.

    Noen viktige problemer med grådige algoritmer er:

    Algoritme Beskrivelse
    Fraksjonert ryggsekk Finn den maksimale totale verdien av gjenstander som kan plasseres i ryggsekken, slik at gjenstander kan inkluderes brøkdeler.
    Dijkstras algoritme Finner den korteste veien fra et kildepunkt til alle andre toppunkter i en vektet graf.
    Kruskals algoritme Finner minimumsspenningstreet i en vektet graf.
    Huffman-koding Oppretter en optimal prefikskode for et sett med symboler, og minimerer den totale kodelengden.

    Relaterte artikler:

    • Veiledning for grådig algoritme
    • Øv problemer på Greedy algoritme

    5. Rekursjon

    Rekursjon er en programmeringsteknikk der en funksjon kaller seg selv innenfor sin egen definisjon. Det brukes vanligvis til å løse problemer som kan brytes ned i mindre forekomster av det samme problemet. For eksempel: Towers of Hanoi (TOH) , Faktoriell beregning og Fibonacci-sekvens etc.

    Trinn :

    • Base Case : Definer en tilstand som stopper de rekursive samtalene og gir en løsning.
    • Rekursivt tilfelle : Definer trinnene for å dele opp problemet i mindre forekomster og foreta rekursive anrop.
    • Komme tilbake : Returner løsningen fra de rekursive samtalene og kombiner dem for å løse det opprinnelige problemet.

    Poenget som gjør rekursjon til en av de mest brukte algoritmene er at den danner grunnlaget for mange andre algoritmer som f.eks. Trekryssinger , Grafoverganger , Divide and Conquer-algoritmer og Tilbakesporingsalgoritmer .

    Relaterte temaer:

    6. Tilbakesporingsalgoritme

    Som nevnt tidligere, Tilbakesporing Algoritmen er avledet fra rekursjonsalgoritmen, med muligheten til å gå tilbake hvis en rekursiv løsning mislykkes, dvs. i tilfelle en løsning mislykkes, sporer programmet tilbake til øyeblikket hvor det mislyktes og bygger på en annen løsning. Så i utgangspunktet prøver den ut alle mulige løsninger og finner den riktige.

    Noen viktige og vanligste problemer med tilbakesporingsalgoritmer, som du må løse før du går videre, er:

    Problem Beskrivelse
    Ridderens turproblem Å finne en sekvens av trekk av en ridder på et sjakkbrett slik at den besøker hver rute nøyaktig én gang.
    Rotte i en labyrint Finne en vei fra startposisjonen til utgangen i en labyrint, med hindringer representert som vegger.
    N-Queen-problem Plassering av N dronninger på et N×N sjakkbrett slik at ingen to dronninger angriper hverandre.
    Delmengde Sum Problem Bestemme om det finnes en delmengde av det gitte settet med en gitt sum.
    Sudoku Løse et 9×9 rutenettpuslespill med tall fra 1 til 9 slik at hver rad, kolonne og 3×3 underrutenett inneholder alle sifrene uten repetisjon.

    Relatert artikkel:

    • Opplæring i tilbakesporing
    • Øv på problemer med tilbakesporingsalgoritme

    7. Dynamisk programmering

    Dynamisk programmering er en metode som brukes i matematikk og informatikk for å løse komplekse problemer ved å bryte dem ned i enklere delproblemer. Ved å løse hvert delproblem bare én gang og lagre resultatene, unngår det overflødige beregninger, noe som fører til mer effektive løsninger for et bredt spekter av problemer.

    Nøkkelkonsepter:

    • Optimal understruktur : Den optimale løsningen på et problem kan konstrueres fra de optimale løsningene til dets delproblemer.
    • Overlappende underproblemer : Delproblemer gjentas ofte i det større problemet, noe som fører til overflødige beregninger.
    • Memoisering / Tabellering : Lagring av løsningene på delproblemer for å unngå omregning.

    Noen viktige og vanligste problemer med dynamiske programmeringsalgoritmer, som du må løse før du går videre, er:

    Problem Beskrivelse
    Fibonacci-sekvens Generering av Fibonacci-tall ved hjelp av dynamisk programmering for å unngå overflødige beregninger.
    Lengste vanlige etterfølge Finne den lengste undersekvensen som er felles for to sekvenser.
    Lengst økende etterfølge Finne den lengste undersekvensen av en gitt sekvens der elementene er sortert i økende rekkefølge.
    0/1 Rullesekkproblem Bestemme den maksimale verdien som kan oppnås ved å velge varer med gitte vekter og verdier, uten å overskride en spesifisert vektgrense.
    Problem med skjæring av stang Maksimere fortjenesten ved å kutte en stang med gitt lengde i biter og selge dem i henhold til gitte priser.
    Myntbytteproblem Bestemme antall måter å gjøre endringer for et gitt beløp ved å bruke et gitt sett med myntvalører.
    Rediger avstand Finne minimum antall operasjoner (innsetting, sletting, substitusjon) som kreves for å konvertere en streng til en annen.
    Delmengde Sum Problem Bestemme om det eksisterer en delmengde av et gitt sett med en gitt sum.
    Lengste palindromiske sekvens Finne den lengste undersekvensen av en gitt sekvens som er et palindrom.
    Maksimal Subarray Sum Finne den sammenhengende undergruppen med den største summen innenfor en gitt endimensjonal matrise.
    Partisjon lik delmengdesum Bestemme om det er mulig å dele et gitt sett i to delsett med lik sum.
    Minimumskostnadsbane Finne minimumskostnadsbanen fra øverste venstre hjørne til nederste høyre hjørne av et gitt rutenett.
    Maksimal produktundergruppe Finne den sammenhengende undergruppen med det største produktet innenfor en gitt endimensjonal matrise.

    Relaterte artikler:

    • Tabulering vs Memoisering
    • Hvordan løser jeg et dynamisk programmeringsproblem?
    • Opplæring i dynamisk programmering
    • Topp 50 kodingsproblemer for dynamisk programmering for intervjuer
    • Øv problemer på dynamisk programmeringsalgoritme

    8. Grafalgoritmer :

    Grafiske algoritmer i datastrukturer og algoritmer (DSA) er et sett med teknikker og metoder som brukes for å løse problemer knyttet til grafer, som er en samling av noder og kanter. Disse algoritmene er designet for å utføre ulike operasjoner på grafer, som f.eks lete, krysse, finne den korteste veien , og bestemme tilkobling . De er avgjørende for å løse et bredt spekter av reelle problemer, inkludert nettverksruting, sosial nettverksanalyse og ressursallokering.

    Emne

    Emnets beskrivelse

    		 Algoritme Algoritmens beskrivelse
    Grafgjennomgang

    Teknikker for å besøke alle toppunkter i en graf.

    		 Depth-First Search (DFS) Utforsker så langt som mulig langs hver gren før den går tilbake.
    Breadth-First Search (BFS) Utforsker nabohjørner før du går til neste nivå med hjørner.

    Minimum spennvidde trær

    Minimum Spanning Trees er de minste trærne som forbinder alle noder i en graf uten å danne sykluser, oppnådd ved å legge til kortest mulig kanter.

    Kruskals algoritme

    Den finner et minimumspenningstre for en tilkoblet vektet graf. Den legger til den minste vektkanten som ikke danner en syklus.

    Prims algoritme

    Den finner også et minimumspenningstre for en tilkoblet vektet graf. Den legger til den minste vektkanten som forbinder to trær.
    Topologisk sortering

    Topologisk sortering er en lineær rekkefølge av toppunktene i en rettet acyklisk graf (DAG) slik at for hver rettet kant fra toppunkt u til toppunkt v, kommer u før v i rekkefølgen.

    		 Kahns algoritme Kahns algoritme finner en topologisk rekkefølge av en rettet asyklisk graf (DAG).
    DFS-basert algoritme DFS-basert algoritme bruker Depth-First Search for å utføre topologisk sortering i en rettet asyklisk graf (DAG).

    Korteste vei

    En korteste vei i en graf er banen mellom to toppunkter i en graf som har minimumssummen av vekter langs kantene sammenlignet med alle andre baner mellom de samme to toppunktene.

    Dijkstras algoritme

    Grådig algoritme for å finne den korteste veien mellom alle noder i O(E * V logV) tid.

    Floyd-Warshall-algoritmen

    Finner den korteste veien mellom alle nodepar i O(V^3) tid.

    Bellman Ford-algoritmen

    Finner den korteste veien fra en enkelt kilde i O(V * E) tid.

    Johnsons algoritme

    Finner de korteste banene mellom alle par av toppunkter i O(V^2 logV + V * E) tid.

    Sterkt tilkoblede komponenter

    En sterkt forbundet komponent (SCC) i en rettet graf er et maksimalt sett med toppunkter slik at det er en vei fra hvert toppunkt i settet til hvert annet toppunkt i settet.

    Kosarajus algoritme

    Kosarajus algoritme er en to-pass algoritme som effektivt finner de sterkt tilkoblede komponentene (SCCs) i en rettet graf.

    Tarjans algoritme

    Tarjans algoritme er en annen effektiv algoritme for å finne SCC-er i en rettet graf

    Relaterte temaer:

    • Grafopplæring
    • Topp 50 grafkodingsproblemer for intervjuer
    • Øv problem på grafalgoritmer

    9 . Mønstersøking

    Mønstersøking er en grunnleggende teknikk i DSA som brukes til å finne forekomster av et spesifikt mønster i en gitt tekst.

    Nedenfor er noen standard mønstersøkealgoritmer:

    Algoritme Beskrivelse Tidskompleksitet
    Ren styrke Den sammenligner mønsteret med hver delstreng i teksten O(mn)
    Knuth-Morris-Pratt Den bruker en forhåndsberegnet feilfunksjon for å hoppe over unødvendige sammenligninger O(m + n)
    Boyer-Moore Den sammenligner mønsteret fra høyre til venstre, og hopper over tegn basert på den siste mismatchen O(mn)
    Rabin-Karp Den bruker hashing for raskt å se etter potensielle treff O(m + n)

    Relaterte temaer:

    • Opplæring i mønstersøking
    • Øve Problem på Mønstersøking

    10 . Matematiske algoritmer

    Matematiske algoritmer er en klasse av algoritmer som løser problemer knyttet til matematiske begreper. De er mye brukt i ulike felt, inkludert datagrafikk, numerisk analyse, optimalisering og kryptografi.

    Algoritme Beskrivelse
    GCD og LCM Finn den største felles divisor og minste felles multiplum av to tall.
    Primtallsfaktorisering Dekomponer et tall i dets primfaktorer.
    Fibonacci tall Generer Fibonacci-sekvensen, der hvert tall er summen av de to foregående.
    Katalanske tall Tell antall gyldige uttrykk med et gitt antall par parenteser.
    Modulær aritmetikk Utfør aritmetiske operasjoner på tall modulo en gitt verdi.
    Euler Totient-funksjon Tell antall positive heltall mindre enn et gitt tall som er relativt prime for det.
    nCr-beregninger Beregn den binomiale koeffisienten, som representerer antall måter å velge r elementer fra et sett med n elementer.
    Primetall og Primalitetstester Bestem om et gitt tall er primtall og finn primtall effektivt.
    Sil algoritmer Finn alle primtall opp til en gitt grense.

    Relaterte temaer:

    • Øv oppgave om matematisk algoritme

    11. Geometriske algoritmer

    Geometriske algoritmer er en klasse av algoritmer som løser problemer knyttet til geometri. Geometriske algoritmer er avgjørende for å løse et bredt spekter av problemer innen informatikk, for eksempel:

    Algoritme Beskrivelse
    Konveks skrog Finner den minste konvekse polygonen som inneholder et sett med punkter.
    Nærmeste poengpar Finner de to punktene i et sett som er nærmest hverandre.
    Linjekryss Bestemmer om to linjer skjærer hverandre og finner i så fall skjæringspunktet.
    Pek i polygon Bestemmer om et gitt punkt er innenfor eller utenfor en polygon.

    Relaterte temaer:

    • Øv deg på geometriske algoritmer

    12. Bitvise algoritmer

    Bitvise algoritmer er algoritmer som opererer på individuelle biter av tall. Disse algoritmene manipulerer den binære representasjonen av tall for å utføre oppgaver som bitmanipulering, bitvise logiske operasjoner (AND, OR, XOR), skiftende biter , og innstilling eller slette spesifikke biter innenfor et tall. Bitvise algoritmer brukes ofte i lavnivå programmering, kryptografi og optimaliseringsoppgaver hvor effektiv manipulering av individuelle biter er nødvendig.

    Emne Beskrivelse
    Bit Shifting Skifter biter til venstre eller høyre med et spesifisert antall posisjoner.
    Venstre skift (<<) Flytter biter til venstre, og multipliserer effektivt tallet med 2.
    Høyre skift (>>) Skifter biter til høyre, og deler tallet med 2.
    Trekk ut biter Bruke masker for å trekke ut spesifikke biter fra et heltall.
    Sette biter Bruke masker for å sette spesifikke biter til 1 i et heltall.
    Rydder biter Bruke masker for å sette spesifikke biter til 0 i et heltall.
    Skiftende biter Bruke XOR (^) for å veksle mellom spesifikke biter i et heltall.
    Telle sett bits Å telle antall settbiter (1s) i et heltall.

    Relaterte temaer:

    • Veiledning for bitvise algoritmer
    • Øv problem på bitvise algoritmer

    13. Randomiserte algoritmer

    Randomiserte algoritmer er algoritmer som bruker tilfeldighet for å løse problemer. De benytter seg av tilfeldige innspill for å nå sine mål, som ofte fører til enklere eller mer effektive løsninger.

    Typer randomiserte algoritmer:

    • Las Vegas : Gir alltid et korrekt resultat, men kjøretiden er tilfeldig.
    • Monte Carlo : Kan gi et feil resultat med liten sannsynlighet, men kjøretiden er vanligvis raskere.

    Viktige algoritmer som bruker randomiseringsalgoritmer:

    Algoritme Beskrivelse
    QuickSort En randomisert sorteringsalgoritme med en gjennomsnittlig sakstidskompleksitet på O(n log n).
    Hopp over liste En randomisert datastruktur som gir raske søke- og innsettingsoperasjoner.
    Bloom Filter En probabilistisk datastruktur for effektiv testing av settmedlemskap.

    14. Gren og bundet algoritme

    De Gren og bundet algoritme er en metode som brukes i kombinatoriske optimaliseringsproblemer for å systematisk søke etter den beste løsningen. Det fungerer ved å dele problemet inn i mindre delproblemer, eller grener, og deretter eliminere visse grener basert på grenser for den optimale løsningen. Denne prosessen fortsetter til den beste løsningen er funnet eller alle grener er utforsket.

    Standardproblemer på gren- og bundet algoritme:

    Unikt problem Beskrivelse
    0/1 Rullesekk med Branch and Bound Implementeringsdetaljer for grenen og bundet tilnærming for å løse 0/1 Knapsack-problemet.
    0/1 Knapsekk med Least Cost Branch and Bound Løser 0/1 Knapsack-problemet ved å bruke den billigste grenen og bundet teknikk.
    8 puslespill Problem med å bruke Branch and Bound Anvendelse av gren og bundet for å løse 8 puslespillproblemet, et populært skyvepuslespill.
    N Queen Problem ved bruk av Branch and Bound Bruker gren og bundet til å finne løsninger på N Queens-problemet, et klassisk sjakkproblem.

    Relaterte temaer:

    • Veiledning for gren og bundet algoritme

    Lær om kompleksiteter

    I Data Structures and Algorithms (DSA) er hovedmålet å løse problemer effektivt. For å bestemme effektiviteten til et program, ser vi på to typer kompleksiteter:

    1. Tidskompleksitet : Dette forteller oss hvor lang tid det tar å kjøre koden vår.
    2. Plass kompleksitet : Dette forteller oss hvor mye minne koden vår bruker.

    Asymptotisk notasjon :

    For å sammenligne effektiviteten til algoritmer bruker vi asymptotisk notasjon, et matematisk verktøy som anslår tid basert på inngangsstørrelse uten å kjøre koden. Den fokuserer på antall grunnleggende operasjoner i programmet.

    Notasjon Beskrivelse
    Big-O (Ο) Beskriver det verste tilfellet, og gir en øvre tidsgrense for algoritmen.
    Omega (Ω) Beskriver det beste scenarioet, og tilbyr en lavere tidsgrense for algoritmen.
    Theta (θ) Representerer den gjennomsnittlige kompleksiteten til en algoritmealgoritme.

    Den mest brukte notasjonen for kodeanalyse er Stor O-notasjon , som gir en øvre grense for kjøretid eller minnebruk angående inngangsstørrelsen.

    merknader i vårstøvel

    Relaterte temaer:

    Øv deg på jukseark:

    Kurserte lister over problemer fra artiklene nedenfor:

    • DSA Roadmap av Sandeep Jain
    • SDE SHEET – En komplett veiledning for SDE-forberedelse
    • techcodeview.com Master Sheet – Liste over alle jukseark