Algoritmi on vaiheittainen menettely ongelman ratkaisemiseksi tai tehtävän suorittamiseksi. Tietorakenteiden ja algoritmien yhteydessä se on joukko hyvin määriteltyjä ohjeita tietyn laskentatehtävän suorittamiseksi. Algoritmit ovat tietojenkäsittelytieteen perusta, ja niillä on erittäin tärkeä rooli tehokkaiden ratkaisujen suunnittelussa erilaisiin ongelmiin. Algoritmien ymmärtäminen on välttämätöntä kaikille tietorakenteiden ja algoritmien hallitsemisesta kiinnostuneille.

Sisällysluettelo

suodatus python

• Mikä on algoritmi?
• Miten algoritmit toimivat?
• Mikä tekee hyvän algoritmin?
• Mikä on algoritmien tarve?
• Esimerkkejä algoritmeista
• Kuinka kirjoittaa algoritmi?
• Opi algoritmien perusteet
• Algoritmien analyysi
• Algoritmien tyypit

Mikä on algoritmi?

An algoritmi on äärellinen sarja hyvin määriteltyjä käskyjä, joita voidaan käyttää laskennallisen ongelman ratkaisemiseen. Se tarjoaa vaiheittaisen menettelyn, joka muuntaa tulon halutuksi lähdöksi.

Miten algoritmit toimivat?

Algoritmit noudattavat yleensä loogista rakennetta:

• Syöte: Algoritmi vastaanottaa syötetiedot.
• Käsittely: Algoritmi suorittaa sarjan operaatioita syöttötiedoille.
• Lähtö: Algoritmi tuottaa halutun tulosteen.

Algoritmin ominaisuudet:

• Selkeä ja yksiselitteinen: Algoritmin tulee olla yksiselitteinen. Jokaisen sen vaiheen tulee olla selkeä kaikilta osin ja johtaa vain yhteen tarkoitukseen.
• Hyvin määritellyt tulot: Jos algoritmi käskee ottaa syötteitä, sen tulee olla hyvin määriteltyjä syötteitä. Se voi ottaa syötteitä tai ei.
• Hyvin määritellyt lähdöt: Algoritmin on määriteltävä selkeästi, mitä tuotos saadaan, ja sen tulee myös olla hyvin määritelty. Sen pitäisi tuottaa vähintään 1 tulos.
• Rajallisuus: Algoritmin on oltava äärellinen, eli sen tulee päättyä äärellisen ajan kuluttua.
• Mahdollinen: Algoritmin on oltava yksinkertainen, yleinen ja käytännöllinen, jotta se voidaan suorittaa kohtuullisilla rajoituksilla ja resursseilla.
• Kielestä riippumaton: Algoritmin on oltava kielestä riippumaton, eli sen on oltava pelkkiä ohjeita, jotka voidaan toteuttaa millä tahansa kielellä, ja silti tulos on odotetusti sama.

Mikä on algoritmien tarve?

Algoritmit ovat välttämättömiä monimutkaisten laskentaongelmien ratkaisemiseksi tehokkaasti ja tehokkaasti. Ne tarjoavat systemaattisen lähestymistavan:

obj javassa

• Ongelmien ratkaiseminen: Algoritmit jakavat ongelmat pienempiin, hallittavissa oleviin vaiheisiin.
• Optimointiratkaisut: Algoritmit löytävät parhaat tai lähes optimaaliset ratkaisut ongelmiin.
• Tehtävien automatisointi: Algoritmit voivat automatisoida toistuvia tai monimutkaisia ​​tehtäviä, mikä säästää aikaa ja vaivaa.

Esimerkkejä algoritmeista

Alla on esimerkkejä algoritmeista:

• Lajittelualgoritmit: Yhdistä lajittelu, pikalajittelu, keon lajittelu
• Hakualgoritmit: Lineaarinen haku, binäärihaku, hajautus
• Graafialgoritmit: Dijkstran algoritmi, Primin algoritmi, Floyd-Warshall-algoritmi
• Merkkijonojen sovitusalgoritmit: Knuth-Morris-Pratt-algoritmi, Boyer-Moore-algoritmi

Kuinka kirjoittaa algoritmi?

Voit kirjoittaa algoritmin seuraavasti:

voiko abstraktilla luokalla olla konstruktori

• Määrittele ongelma: Ilmoita selkeästi ratkaistava ongelma.
• Suunnittele algoritmi: Valitse sopiva algoritmisuunnitteluparadigma ja kehitä vaiheittainen menettely.
• Toteuta algoritmi: Käännä algoritmi ohjelmointikielelle.
• Testaa ja korjaa: Suorita algoritmi eri syötteillä varmistaaksesi sen oikeellisuuden ja tehokkuuden.
• Analysoi algoritmi: Määritä sen aika- ja tilamonimutkaisuus ja vertaa sitä vaihtoehtoisiin algoritmeihin.

Opi algoritmien perusteet

• Mikä on algoritmi | Johdatus algoritmeihin
• Määritelmä, tyypit, monimutkaisuus, esimerkit algoritmeista
• Algoritmien suunnittelutekniikat
• Miksi algoritmin analysointi on tärkeää?

Algoritmien analyysi

• Asymptoottinen analyysi
• Huonoin, keskimääräinen ja paras tapaus
• Asymptoottiset merkinnät
• Ala- ja ylärajan teoria
• Johdatus jaksotettuun analyysiin
• Mitä 'tilan monimutkaisuus' tarkoittaa?
• Polynomiajan approksimaatiokaavio
• Kirjanpitomenetelmä | Poistettu analyysi
• Potentiaalinen menetelmä jaksotettuun analyysiin

Algoritmien tyypit

Algoritmit voivat olla erilaisia ​​sen mukaan, mitä ne tekevät ja miten ne on tehty. Joitakin yleisiä tyyppejä ovat:

1. Haku- ja lajittelualgoritmit

• Johdatus hakualgoritmiin
• Johdatus lajittelualgoritmiin
• Vakaat ja epävakaat lajittelualgoritmit
• Vertailupohjaisten lajittelualgoritmien alaraja
• Voiko vertailupohjaisen lajittelualgoritmin ajonaikaisen monimutkaisuuden olla pienempi kuin N logN?
• Mikä lajittelualgoritmi tekee minimimäärän muistikirjoituksia?

2. Ahneet algoritmit

• Johdatus ahneisiin algoritmeihin
• Toiminnon valintaongelma
• Huffman koodaus
• Työn järjestysongelma
• Tietovisa ahneista algoritmeista
• Rautatie-/linja-autoasemalle vaadittava laiturien vähimmäismäärä

3. Dynaamiset ohjelmointialgoritmit

• Johdatus dynaamiseen ohjelmointiin
• Päällekkäiset aliongelmat -ominaisuus
• Optimaalinen alustan ominaisuus
• Pisin kasvava jakso
• Pisin yhteinen jakso
• Pienin kustannuspolku
• Kolikon vaihto
• Matriisiketjun kertolasku
• 0-1 Reppuongelma
• Pisin palindrominen alajakso
• Palindromin osiointi

4. Kuvionhakualgoritmit

• Johdatus kuvionhakuun
• Naiivi kuvion haku
• KMP-algoritmi
• Rabin-Karp -algoritmi
• Kuviohaku kaikkien päätteiden triellä
• Aho-Corasickin algoritmi kuvioiden etsimiseen
• Z-algoritmi (lineaarisen aikakuvion etsintäalgoritmi)

5. Paluualgoritmi

• Johdatus Backtrackingiin
• Tulosta kaikki tietyn merkkijonon permutaatiot
• Ritarin kiertueen ongelma
• Rotta sokkelossa
• N Queen -ongelma
• Osajoukon summa
• m Väritysongelma
• Hamiltonin sykli
• Sudoku

6. Jaa ja hallitse -algoritmi

• Johdatus hajota ja hallitse
• Yhdistä lajittelu
• Kirjoita oma pow(x, n) laskeaksesi x*n
• Laske inversiot
• Lähin pistepari
• Strassenin matriisikertolasku

7. Geometrinen algoritmi

• Johdatus geometrisiin algoritmeihin
• Lähin pistepari | O(nlogn) Toteutus
• Kuinka tarkistaa, onko tietty piste polygonin sisällä vai ulkopuolella?
• Kuinka tarkistaa, leikkaavatko kaksi annettua janaa?
• Kun on annettu n janaa, selvitä, leikkaavatko mitkään kaksi janaa
• Kuinka tarkistaa, muodostaako annettu neljä pistettä neliön
• Kupera runko käyttämällä Jarvisin algoritmia tai käärettä

8. Matemaattiset algoritmit

• Johdatus matemaattisiin algoritmeihin
• Kirjoita tehokas menetelmä tarkistaaksesi, onko luku 3:n monikerta
• Kirjoita ohjelma kahden luvun lisäämiseksi kantaan 14
• Ohjelma Fibonacci-numeroille
• Numerovirran keskiarvo
• Kerro kaksi kokonaislukua ilman kerto-, jako- ja bittikohtaisia ​​operaattoreita ja ilman silmukoita
• Babylonian menetelmä neliöjuurelle
• Eratosthenesin seula
• Pascalin kolmio
• Anna numero, etsi seuraavaksi pienin palindromi
• Ohjelma lisäämään kaksi polynomia
• Kerro kaksi polynomia
• Laske luvun lopussa olevat nollat ​​kertoimella

9. Bittikohtaiset algoritmit

• Bitwise-algoritmien esittely
• Pikku ja iso endian
• Tunnista päinvastaiset merkit
• Vaihda bittejä
• Sammuta oikeanpuoleisin asetettu bitti
• Pyöritä bittejä
• Seuraavaksi suurempi numero samalla määrällä asetettuja bittejä
• Vaihda kaksi nibbleä tavussa

10. Graafialgoritmit

• Johdatus satunnaistettuihin algoritmeihin
• Odotuksen lineaarisuus
• Kokeilujen odotettu määrä onnistumiseen asti
• Satunnaistetut algoritmit | Sarja 0 (matemaattinen tausta)
• Satunnaistetut algoritmit | Sarja 1 (johdanto ja analyysi)
• Satunnaistetut algoritmit | Sarja 2 (luokitus ja sovellukset)
• Satunnaistetut algoritmit | Sarja 3 (1/2 likimääräinen mediaani)
• Näytteenotto säiliöstä