i programmerere er livsalgoritmer og datastrukturer det viktigste emnet hvis de ønsker å gå ut i programmeringsverdenen og gjøre noen dollar. I dag ser vi hva de gjør og hvor de brukes med enkleste eksempler. Denne listen er utarbeidet med tanke på deres bruk i konkurransedyktig programmering og nåværende utviklingspraksis.

Sorteringsalgoritmer

Sortering Er Det mest studerte konseptet Innen Informatikk. Ideen er å ordne elementene i en liste i en bestemt rekkefølge. Selv om alle store programmeringsspråk har innebygde sorteringsbiblioteker, kommer det til nytte hvis du vet hvordan de fungerer. Avhengig av kravet kan du bruke noen av disse.

• Slå Sammen Sortering
• Rask Sortering
• Bøtte Sortering
• Heap Sortering
• Telle Sortering

Enda viktigere man bør vite når og hvor du skal bruke dem. Noen eksempler hvor du kan finne direkte anvendelse av sorteringsteknikker inkluderer:

• Sortering etter pris, popularitet etc i e-handelsnettsteder

Søkealgoritmer

Binært Søk (i lineære datastrukturer)

Binært søk brukes til å utføre et svært effektivt søk på sorterte datasett. Tidskompleksiteten Er O (log2N). Ideen er å gjentatte ganger dele i halvparten av listen som kan inneholde elementet, til vi begrenser det til ett mulig element. Noen programmer er:

• når du søker etter et navn på sangen i en sortert liste over sanger, utfører binær søk og streng-matching for raskt å returnere resultatene.
• Brukes til å feilsøke i git gjennom git bisect

Dybde / Bredde Første Søk (I Graf datastrukturer)

DFS og BFS er tre / graf traversering og søker datastrukturer. Vi ville ikke gå dypt inn i HVORDAN DFS / BFS fungerer, men vil se hvordan de er forskjellige gjennom følgende animasjon.

Programmer:

• Brukes av søkemotorer for web-gjennomgang
• Brukes i kunstig intelligens til å bygge roboter, for eksempel en sjakk bot
• Finne korteste vei mellom to byer i et kart og mange andre slike programmer

Hashing

hash lookup er for tiden den mest brukte teknikken for å finne passende data etter nøkkel eller id. Vi får tilgang til data ved sin indeks. Tidligere stolte vi På Sortering + Binært Søk for å lete etter indeks mens vi nå bruker hashing.datastrukturen refereres som Hash-Kart eller Hash-Bord eller Ordbok som kartlegger nøkler til verdier, effektivt. Vi kan utføre verdi oppslag ved hjelp av nøkler. Ideen er å bruke en passende hash-funksjon som gjør nøkkelen- > verdi kartlegging. Å velge en god hash-funksjon avhenger av scenariet.

Applikasjoner:

• i rutere, for å lagre IP-adresse – > Banepar for rutemekanismer
• for å sjekke om en verdi allerede finnes i en liste. Lineært søk ville være dyrt. Vi kan også bruke Sett datastruktur for denne operasjonen.

Dynamisk Programmering

Dynamisk programmering (Dp) Er en metode for å løse et komplekst problem ved å bryte det ned i enklere delproblemer. Vi løser delproblemene, husker resultatene og bruker dem til å løse det komplekse problemet raskt.

*skriver ned «1+1+1+1+1+1+1+1 =» på et ark* Hva er det lik?
*teller* Åtte!
*skriver ned en annen «1+» til venstre* Hva med det?
*raskt* Ni!hvordan visste du at det var ni så fort?
Du har nettopp lagt til en mer
slik at du ikke trenger å fortelle fordi du husket det var åtte! Dynamisk Programmering er bare en fancy måte å si ‘huske ting for å spare tid senere’

Programmer:

• Det er mange dp algoritmer og programmer, men jeg vil nevne en og blåse deg bort, Duckworth-Lewis metode i cricket.

Eksponentiering ved kvadrering

Si at du vil beregne 232. Normalt vil vi iterere 32 ganger og finne resultatet. Hva om jeg fortalte deg at det kan gjores i 5 iterasjoner?eksponentiering ved kvadrering eller Binær eksponering er en generell metode for rask beregning av store positive heltallskrefter Av et tall I o(log2N). Ikke bare dette, metoden brukes også til beregning av krefter av polynomer og firkantede matriser.

Søknad:

• Beregning av store krefter av et tall er for det meste nødvendig I RSA-kryptering. RSA bruker også modulær aritmetikk sammen med binær eksponering.

String Matching og Parsing

Mønstermatching / søking er et av De viktigste problemene Innen Datavitenskap. Det har vært mye forskning på emnet, men vi får bare to grunnleggende nødvendigheter for enhver programmerer.

Kmp Algoritme (String Matching)

Knuth-Morris-Pratt algoritme brukes i tilfeller der vi må matche et kort mønster i en lang streng. For Eksempel, Når Vi Ctrl + F et søkeord i et dokument, utfører vi mønstermatching i hele dokumentet.Regulært Uttrykk (Strengparsing)

Mange ganger må vi validere en streng ved å analysere over en forhåndsdefinert begrensning. Det er tungt brukt i webutvikling FOR URL parsing og matching.

Primalitetstestalgoritmer

Det er deterministiske og probabilistiske måter å bestemme om et gitt tall er primtall eller ikke. Vi ser både deterministiske og probabilistiske (ikke-deterministiske) måter.Hvis vi har viss grense på rekkevidden av tall, si bestemme alle primene innenfor området 100 til 1000, Så Er Sieve en vei å gå. Lengden på rekkevidde er en avgjørende faktor, fordi vi må tildele viss mengde minne i henhold til rekkevidde.hvis du vil sjekke for få tall som er tynt spredt over et langt område (si 1 til 1012), Vil Sieve ikke kunne tildele nok minne. Du kan sjekke for hvert nummer n ved å krysse bare opp til sqrt(n) og utføre en delbarhetskontroll på n.

Fermat primality test og Miller-Rabin primality test (begge er ikke-deterministiske)

Begge disse er kompositthetstester. Hvis et tall er bevist å være sammensatt, så er det sikkert ikke et primtall. Miller-Rabin er en mer sofistikert enn Fermats. Infact, Miller-Rabin har også en deterministisk variant, men da er det et spill av handel mellom tidskompleksitet og nøyaktighet av algoritmen.

Søknad:

• den viktigste bruken av primtall er I Kryptografi. Mer presist, de brukes i kryptering og dekryptering I rsa algoritme som var den aller første gjennomføringen Av Public Key Cryptosystems