algoritmeissä

Algoritmi on selkeästi määritelty, askel kerrallaan suoritettava menettely, jolla ratkaistaan tietty ongelma. Algoritmeissä korostuvat oikeellisuus, loppuun saattavuus sekä määritelty syöte ja tuloste. Ne toteutuvat ohjelmointikielen avulla ja voivat käsitellä erilaista dataa sekä käyttää erilaisia tietorakenteita. Hyvä algoritmi tuottaa oikean tuloksen tehokkaasti ja luotettavasti.

Algoritmeissä suunnittelua ohjaavat tunnetut periaatteet: jakaminen ja valloittaminen (divide and conquer), dynaaminen ohjelmointi, ahneat menetelmät, takaisinjäljitys sekä satunnaiset menetelmät. Ne voivat olla deterministisiä tai satunnaistettuja ja voivat olla sekä iteratiivisia että rekursiivisia. Tietorakenteet kuten taulukot, puut ja grafit vaikuttavat olennaisesti.

Tehokkuutta arvioidaan ajassa ja tilassa. Aikavaativuus ilmaistaan tavallisesti Big O -merkintöinä; tilavaativuus kuvaa muistinkäyttöä. Arviointi tehdään sekä pahimmassa tapauksessa (worst-case) että keskimäärin (average-case); joskus käytetään myös amortisoitua analyysia.

Esimerkkejä ovat lajittelualgoritmit kuten quicksort ja mergesort, hakualgoritmit kuten binäärinen haku sekä graafialgoritmit kuten Dijkstra, Bellman-Ford, Kruskal ja Prim. Merkkijonoalgoritmit kuten Knuth–Morris–Pratt sekä Boyer–Moore -hakumenetelmät kuuluvat myös laajasti käytettyihin työkaluihin. Algoritmejä sovelletaan tietojenkäsittelyn eri osa-alueisiin ja monimutkaisten ongelmien optimointiin sekä analysointiin.

Algoritmeihin liittyvä tutkimus on keskeinen osa tietojenkäsittelystä ja ohjelmistokehitystä. Sen teoreettinen perusta muodostuu laskennan malleista sekä kompleksisuusteoriasta, ja alalla yhdistyy käytännön ongelmanratkaisu sekä teoreettinen analyysi.