Hajota ja hallitse -yhtälö ja algoritmin tehokkuus

Abstract

Algoritmien tehokkuus on olennaista algoritmeja suunniteltaessa. Tutkielmassa käsitellään algoritmien tehokkuutta, hajota ja hallitse -yhtälön käyttöä algoritmien kehittämisessä sekä rekursiivisten funktioiden asymptoottisen tehokkuuden arviointitapoja. Tutkielmassa käytetään lähteinä teoksia Discrete Mathematics with Applications ja Introduction to Algorithms.

Jotta kahden algoritmin tehokkuuksia voidaan verrata keskenään, on löydettävä tapa, jolla voimme objektiivisesti arvioida algoritmien tehokkuutta. Tätä varten tutkielmassa määritellään ordo-, omega- ja theta-notaatiot. Tutkielmassa myös annetaan näiden käytöstä esimerkit. Ordo-notaatio kertoo algoritmin vaatiman maksimaalisen ajankäytön, omega-notaatio puolestaan kertoo algoritmin vaatiman minimaalisen ajankäytön. Theta-notaatio yhdistää ordo- ja omega-notaatiot ja antaa arvion algoritmin vaatimasta keskivertoajankäytöstä.

Rekursiiviset funktiot ovat funktioita, jotka määritellään perustapauksen, sekä funktion aikaisempien arvojen perusteella. Rekursiiviset algoritmit ovat algoritmeja, jotka kutsuvat itseään uudella arvolla, kunnes pääsemme triviaalitapaukseen. Tutkielmassa on annettu tarkemmat määritelmät rekursiivisille funktioille ja algoritmeille.

Jotta rekursiivisten algoritmien tehokkuuksia voidaan vertailla, tarvitsee löytää tapa, jolla mallintaa niiden tehokkuuksia aikaisempien notaatioiden avulla. Tätä varten tutkielmassa käydään läpi rekursiopuut, sekä päämetodi. Rekursiopuu antaa meille graafisen kuvauksen algoritmin toiminnasta, jonka perusteella on mahdollista tehdä arvio algoritmin ajankäytöstä, ja tämän jälkeen todistaa arvio oikeaksi induktiotodistuksella. Päämetodi soveltuu algoritmeihin, joiden toimintaa voi kuvata hajota ja hallitse -yhtälöllä. Tutkielmassa käydään läpi päämetodin kolme tapausta, sekä todistetaan päämetodin toimivuus.

Tutkielman lopussa käydään läpi hajota ja hallitse -periaate algoritmien suunnittelussa. Tästä tutkielmassa käydään esimerkkinä läpi lomituslajittelu ja arvioidaan sen asymptoottinen tehokkuus päämetodin avulla.