Home-theater-designersOhjelmoinnin opiskelijana olet todennäköisesti oppinut paljon erilaisia algoritmeja urasi aikana. Eri algoritmien hallitseminen on ehdottoman välttämätöntä jokaiselle ohjelmoijalle.
Niin monen algoritmin avulla voi olla haastavaa seurata olennaista. Jos valmistaudut haastatteluun tai vain harjaat taitojasi, tämä luettelo tekee siitä suhteellisen helppoa. Lue, kun luettelemme ohjelmoijille tärkeimmät algoritmit.
1. Dijkstran algoritmi
Edsger Dijkstra oli aikansa vaikutusvaltaisimpia tietotekniikan tutkijoita, ja hän osallistui monille eri laskentatieteen aloille, mukaan lukien käyttöjärjestelmät, kääntäjärakentaminen ja paljon muuta. Yksi Dijkstran merkittävimmistä panoksista on hänen lyhyimmän reittialgoritminsa kekseliäisyys, joka tunnetaan myös nimellä Dijkstran lyhin polkualgoritmi.
Dijkstran algoritmi löytää kaavion lyhyimmän polun lähteestä kaikkiin kuvaajan kärkiin. Jokaiseen algoritmin iterointiin lisätään kärki, jonka minimietäisyys lähteestä on sellainen, jota ei ole nykyisellä lyhyimmällä polulla. Tämä on ahne ominaisuus, jota Djikstran algoritmi käyttää.
Algoritmi toteutetaan tyypillisesti käyttämällä sarjaa. Dijkstran algoritmi on erittäin tehokas, kun se toteutetaan Min Heapilla; löydät lyhyimmän polun vain O (V+ElogV) -ajalla (V on pisteiden lukumäärä ja E on tietyn kaavion reunojen määrä).
Dijkstran algoritmilla on rajoituksensa; se toimii vain suunnatuissa ja suunnattomissa kaavioissa, joiden reunat ovat positiivisia. Negatiivisille painoille Bellman-Ford-algoritmi on tyypillisesti parempi.
Haastattelukysymykset sisältävät yleensä Djikstran algoritmin, joten suosittelemme ymmärtämään sen monimutkaisia yksityiskohtia ja sovelluksia.
2. Yhdistä lajittelu
Tässä luettelossa on pari lajittelualgoritmia, ja yhdistämislajittelu on yksi tärkeimmistä algoritmeista. Se on tehokas lajittelualgoritmi, joka perustuu Divide and Conquer -ohjelmointitekniikkaan. Pahimmassa tapauksessa yhdistämislajittelu voi lajitella n lukua vain O (nlogn) -ajalla. Verrattuna primitiivisiin lajittelutekniikoihin, kuten Kuplan lajittelu (se vie O (n^2) aikaa), yhdistämislaji on erittäin tehokas.
Aiheeseen liittyviä: Johdatus yhdistämislajittelualgoritmiin
Yhdistämislajittelussa lajiteltava matriisi jaetaan toistuvasti osajoukkoihin, kunnes kukin aliryhmä koostuu yhdestä numerosta. Rekursiivinen algoritmi yhdistää sitten toistuvasti alijoukkoja ja lajittelee taulukon.
kuinka käynnistää Android vikasietotilassa
3. Pikavalinta
Quicksort on toinen lajittelualgoritmi, joka perustuu Divide and Conquer -ohjelmointitekniikkaan. Tässä algoritmissa elementti valitaan ensin pivotiksi ja koko taulukko osioidaan tämän pivotin ympärille.
Kuten olet todennäköisesti arvannut, hyvä nivel on ratkaiseva tehokkaan lajittelun kannalta. Pivot voi olla joko satunnainen elementti, mediaelementti, ensimmäinen elementti tai jopa viimeinen elementti.
Pikavalinnan toteutukset vaihtelevat usein siinä, miten ne valitsevat kääntöpisteen. Keskimääräisessä tapauksessa quicksort lajittelee suuren taulukon hyvällä kääntöpisteellä vain O (nlogn) -ajalla.
Pikavalinnan yleinen pseudokoodi osittaa taulukon toistuvasti pivotissa ja sijoittaa sen alirivin oikeaan paikkaan. Se sijoittaa myös elementit, jotka ovat pienempiä kuin kääntöpiste vasemmalle, ja elementit, jotka ovat suurempia kuin nivel oikealle.
4. Syvyys ensimmäinen haku
Syvyys ensimmäinen haku (DFS) on yksi ensimmäisistä kaavion algoritmeista, joita opetti opiskelijoille. DFS on tehokas algoritmi, jota käytetään kuvaajan siirtymiseen tai hakuun. Sitä voidaan myös muokata käytettäväksi puiden läpikulussa.
DFS -läpivienti voi alkaa mistä tahansa mielivaltaisesta solmusta ja sukeltaa jokaiseen viereiseen huippuun. Algoritmi perääntyy, kun ei ole vierailtua kärkeä tai on umpikuja. DFS toteutetaan tyypillisesti pinolla ja boolen matriisilla, jolla seurataan vierailtuja solmuja. DFS on yksinkertainen toteuttaa ja poikkeuksellisen tehokas; se toimii (V+E), missä V on kärkien lukumäärä ja E on reunojen lukumäärä.
DFS -läpikulun tyypillisiä sovelluksia ovat topologinen lajittelu, syklien havaitseminen kaaviossa, polun etsiminen ja vahvasti kytkettyjen komponenttien löytäminen.
5. Leveys-ensimmäinen haku
Leveys-ensimmäinen haku (BFS) tunnetaan myös puiden tasojärjestyksenä. BFS toimii O (V+E) -tilassa DFS -algoritmin tavoin. BFS käyttää kuitenkin pinon sijaan jonoa. DFS sukeltaa kuvaajaan, kun taas BFS kulkee kuvaajan leveyssuunnassa.
kuinka lajitella lähettäjän mukaan gmailissa
BFS -algoritmi käyttää jonoa pisteiden seurantaan. Vierailevissa vierekkäisissä kärkipisteissä vieraillaan, merkitään ja jonotetaan. Jos kärjessä ei ole viereistä kärkeä, piste poistetaan jonosta ja tutkitaan.
BFS: ää käytetään yleisesti vertaisverkoissa, painottamattoman kaavion lyhimmällä polulla ja pienimmän puun löytämiseksi.
6. Binaarinen haku
Binaarihaku on yksinkertainen algoritmi tarvittavan elementin löytämiseksi lajitellusta taulukosta. Se toimii jakamalla taulukko toistuvasti puoliksi. Jos vaadittu elementti on pienempi kuin keskimmäinen elementti, keskielementin vasenta puolta käsitellään edelleen; Muussa tapauksessa oikea puoli puolitetaan ja etsitään uudelleen. Prosessi toistetaan, kunnes tarvittava elementti löytyy.
Binaarihaun pahimman ajan monimutkaisuus on O (logn), mikä tekee siitä erittäin tehokkaan etsimään lineaarisia matriiseja.
7. Vähimmäispuitealgoritmit
Kaavion vähimmäispituuspuulla (MST) on vähimmäiskustannukset kaikkien mahdollisten ulottuvuuspuiden joukossa. Jousivan puun hinta riippuu sen reunojen painosta. On tärkeää huomata, että minimipituuspuita voi olla useita. MST -algoritmeja on kaksi, nimittäin Kruskal ja Prim.
Kruskalin algoritmi luo MST: n lisäämällä reunan pienin kustannuksin kasvavaan joukkoon. Algoritmi lajittelee reunat ensin niiden painon mukaan ja lisää sitten reunat MST: hen alkaen minimistä.
On tärkeää huomata, että algoritmi ei lisää sykliä muodostavia reunoja. Kruskalin algoritmi on edullinen harvakaavioille.
Primin algoritmi käyttää myös ahneutta ja on ihanteellinen tiheille kaavioille. Primin MST: n keskeinen ajatus on, että siinä on kaksi erillistä kärkipisteitä; toinen joukko sisältää kasvavaa MST: tä, kun taas toinen sisältää käyttämättömiä kärkipisteitä. Jokaisessa iteroinnissa valitaan vähimmäispaino, joka yhdistää nämä kaksi sarjaa.
Vähimmäispituuspuun algoritmit ovat välttämättömiä klusterianalyysille, taksonomialle ja yleislähetysverkoille.
Tehokas ohjelmoija osaa algoritmeja
Ohjelmoijat opiskelevat ja kehittävät jatkuvasti taitojaan, ja joidenkin perustaitojen on oltava taitavia. Taitava ohjelmoija tuntee erilaiset algoritmit, kunkin edut ja haitat sekä sen, mikä algoritmi sopisi parhaiten tiettyyn tilanteeseen.
hauskoja asioita vadelma pi kanssaJaa Jaa Tweet Sähköposti Johdanto Shell -lajittelualgoritmiin
Vaikka kuoren lajittelu ei ole tehokkain tapa, aloittelijoilla on paljon hyötyä sen harjoittamisesta.
Lue seuraava Liittyvät aiheet- Ohjelmointi
- Ohjelmointi
- Algoritmit
Fahad on MakeUseOfin kirjailija ja hän on tällä hetkellä pääaineena tietotekniikka. Innokkaana teknikkona hän varmistaa, että hän pysyy ajan tasalla uusimmasta tekniikasta. Hän on erityisen kiinnostunut jalkapallosta ja tekniikasta.
Lisää M. Fahad Khawajaltatilaa uutiskirjeemme
Liity uutiskirjeeseemme saadaksesi teknisiä vinkkejä, arvosteluja, ilmaisia e -kirjoja ja ainutlaatuisia tarjouksia!
Klikkaa tästä tilataksesi