ohjelmoijissa elämänalgoritmit ja tietorakenteet on tärkein aihe, jos he haluavat lähteä ohjelmointimaailmaan ja tehdä some taalaa. Tänään näemme, mitä ne tekevät ja missä niitä käytetään yksinkertaisimmilla esimerkeillä. Tämä lista on laadittu pitäen mielessä niiden käyttö kilpailukykyisessä ohjelmoinnissa ja nykyisissä kehityskäytännöissä.

Lajittelualgoritmit

lajittelu on tietojenkäsittelytieteen tutkituin käsite. Ideana on järjestää listan kohteet tiettyyn järjestykseen. Vaikka jokaisella suurella ohjelmointikielellä on sisäänrakennetut lajittelukirjastot, se on kätevä, jos tiedät, miten ne toimivat. Riippuen vaatimus saatat haluta käyttää jotain näistä.

• Merge Sort
• Quick Sort
• Bucket Sort
• Heap Sort
• Counting Sort

tärkeämpää on tietää, milloin ja missä niitä käytetään. Esimerkkejä lajittelutekniikoiden suorasta soveltamisesta ovat:

• Lajittelu hinnan, suosion jne.mukaan verkkokauppasivustoilla

hakualgoritmit

Binäärihakua (lineaarisissa tietorakenteissa)

Binäärihakua käytetään erittäin tehokkaaseen hakuun lajitellussa aineistossa. Ajallinen monimutkaisuus on O (log2N). Ajatuksena on toistuvasti jakaa puoleen se osa luettelosta, joka voisi sisältää kohteen, kunnes rajaamme sen yhteen mahdolliseen kohtaan. Jotkin sovellukset ovat:

• kun etsit kappaleen nimeä lajitellusta kappaleluettelosta, se suorittaa binäärihaun ja merkkijonosovituksen palauttaakseen tulokset nopeasti.
• käytetään vianetsintään git: ssä git: n puolittamisen kautta

syvyys/leveys ensimmäinen haku (kaavion tietorakenteissa)

DFS ja BFS ovat puun / kaavion läpikäyviä ja hakevia tietorakenteita. Emme menisi syvälle miten DFS / BFS toimivat, mutta nähdä, miten ne ovat erilaisia kautta seuraava animaatio.

Sovellukset:

• hakukoneiden verkkohyökkäykseen käyttämä
• käytetään tekoälyssä bottien rakentamiseen, esimerkiksi shakkibotti
• löytää lyhimmän polun kahden kaupungin välillä kartalla ja monet muut tällaiset sovellukset

Hashing

hash-haku on tällä hetkellä yleisimmin käytetty tekniikka, jolla etsitään sopivaa tietoa avaimen tai ID: n avulla. Pääsemme tietoihin sen indeksin avulla. Aiemmin luotimme Lajittelu + Binary Haku etsiä indeksiä, kun nyt käytämme hashing.

tietorakenteesta käytetään nimitystä Hash-Map tai Hash-Table tai sanakirja, joka kartoittaa arvojen avaimia tehokkaasti. Voimme suorittaa arvohakuja näppäimillä. Ideana on käyttää sopivaa hajautusfunktiota, joka tekee avaimen – > arvon kartoitus. Hyvän hajautusfunktion valinta riippuu skenaariosta.

Sovellukset:

• reitittimissä IP-osoitteen tallentamiseksi – > Reititysmekanismien Polkupari
• suorittaa tarkistuksen, jos luettelossa on jo arvo. Lineaarinen haku olisi kallista. Voimme myös käyttää Set-tietorakennetta tähän operaatioon.

dynaaminen ohjelmointi

dynaaminen ohjelmointi (DP) on menetelmä monimutkaisen ongelman ratkaisemiseksi hajottamalla se yksinkertaisempiin osaongelmiin. Ratkaisemme osaongelmat, muistamme niiden tulokset ja niiden avulla selvitämme monimutkaisen ongelman nopeasti.

* kirjoittaa ylös ”1+1+1+1+1+1+1+1 =” paperiarkilla * mitä se vastaa?
* counting * Eight!
*kirjoittaa ylös toisen ”1+” vasemmalla* entäs tuo?
* nopeasti * yhdeksän!
How ’ d you know it was nine so fast?
lisäsitte vain yhden
, joten teidän ei tarvinnut laskea uudelleen, koska muistitte, että niitä oli kahdeksan! Dynaaminen ohjelmointi on vain hieno tapa sanoa ”remembering stuff to save time later”

Sovellukset:

• on monia DP-algoritmeja ja sovelluksia, mutta nimeäisin yhden ja räjäyttäisin sinut pois, Duckworth-Lewis metodi kriketissä.

eksponentiaatio neliöimällä

sano, että haluat laskea 232. Normaalisti toistaisimme 32 kertaa ja löytäisimme tuloksen. Mitä jos kerron, että se voidaan tehdä 5 iterations?

Eksponentaatio neliöimällä tai binäärinen eksponentaatio on yleinen menetelmä suurten positiivisten kokonaislukujen O-luvun potenssien(log2N) nopeaan laskemiseen. Tämän lisäksi menetelmää käytetään myös polynomien ja neliömatriisien valtuuksien laskemiseen.

sovellus:

• suurien potenssien laskeminen vaaditaan useimmiten RSA-salauksessa. RSA käyttää myös modulaarista aritmetiikkaa binäärisen eksponentaation ohella.

merkkijonojen sovittaminen ja jäsentäminen

Pattern matching / searching on tietojenkäsittelytieteen tärkeimpiä ongelmia. Aiheesta on tehty paljon tutkimusta, mutta värväämme ohjelmoijille vain kaksi perustarvetta.

KMP-algoritmia (Merkkijonosovitus)

Knuth-Morris-Pratt-algoritmia käytetään tapauksissa, joissa on sovitettava lyhyt kuvio pitkään merkkijonoon. Esimerkiksi, kun me Ctrl + F avainsana asiakirjassa, suoritamme kuvio matching koko asiakirjan.

säännöllinen lauseke (merkkijonojen jäsennys)

monta kertaa joudumme vahvistamaan merkkijonon jäsentämällä ennalta määritellyn rajoituksen yli. Sitä käytetään runsaasti verkkokehityksessä URL-jäsennykseen ja sovittamiseen.

Primaalisuuden Testausalgoritmeja

on olemassa deterministisiä ja todennäköisyysabilistisia tapoja määrittää, onko tietty luku alkuluku vai ei. Näemme sekä deterministisiä että probabilistisia (ei-deterministisiä) tapoja.

seula Eratosthenes (deterministinen)

Jos meillä on tietty raja-alue lukujen, sano määrittää kaikki alkuluvut alueella 100-1000 sitten seula on tapa mennä. Kantaman pituus on ratkaiseva tekijä, koska meidän on varattava tietty määrä muistia kantaman mukaan.

mille tahansa luvulle n, inkrementaalisesti testaten upto sqrt(n) (deterministinen)

Jos haluat tarkistaa muutaman luvun, jotka ovat harvaan jakautuneet pitkälle alueelle (vaikkapa 1-1012), seula ei pysty varaamaan tarpeeksi muistia. Voit tarkistaa jokaisen luvun n kulkemalla vain ylöspäin sqrt: hen(n) ja tehdä jaettavuustarkastuksen N: lle.

Fermat ’ n primaarisuustesti ja Miller–Rabin primaarisuustesti (molemmat ovat nondeterministisiä)

molemmat ovat koostumustestejä. Jos luku todistetaan yhdistelmäksi, se ei todellakaan ole alkuluku. Miller-Rabin on kehittyneempi kuin Fermat ’ n. Infact, Miller-Rabin on myös deterministinen variantti, mutta sitten sen peli kaupan välillä aika monimutkaisuus ja tarkkuus algoritmin.

hakemus:

• tärkein yksittäinen alkulukujen käyttö on kryptografiassa. Tarkemmin niitä käytetään salauksessa ja salauksen purkamisessa RSA-algoritmissa, joka oli aivan ensimmäinen julkisen avaimen Kryptosysteemien toteutus
• toinen käyttö on Hajautustaulukoissa käytetyissä Hajautusfunktioissa