Lyhyt MathCheck-ohje (uuteen välilehteen)
Algoritmien nopeus, muistin kulutus tai muu resurssien kulutus saattaa riippua syötteen koosta monella eri tavalla. On tavallista ilmaista tämä riippuvuus isolla O-, Ω- tai Θ-merkinnällä. Tässä tehtävässä tutustutaan niihin. Konkretian vuoksi puhumme ajan kulutuksesta, mutta käsiteltävät asiat pätevät myös muistin jne. kulutukseen.
Aloitamme esimerkillä, joka havainnollistaa valintatilannetta, jonka kaltaisia tulee ohjelmoinnissa usein vastaan. Tehtävään on tarjolla kaksi vaihtoehtoista algoritmia. Algoritmi A on yksinkertainen ja helppo ohjelmoida. Sen millisekunteina mitattu ajan kulutus syötteen koon `n` funktiona noudattaa lauseketta `n^2/50+1`. (Yksi sekunti on 1000 millisekuntia.) Algoritmi B on monimutkainen ja vaikea ohjelmoida. Sen millisekunteina mitattu ajan kulutus syötteen koon `n` funktiona noudattaa lauseketta `n log n+10`.
Kumpi algoritmi kannattaa valita seuraavissa tilanteissa? Vastaa A tai B.
Toivottavasti nämä esimerkit riittivät vakuuttamaan, että vaikka B on vaikea toteuttaa ja pienillä syötteillä hitaampi kuin A, se on silti yleensä paras valinta. A on selvästi paras vain jos on varmaa, että suurin koskaan esiintyvä syöte on pieni. Yleensä syötekokoja koskeva tieto on puutteellista. Yksikin iso syöte saattaa viedä A:lla niin paljon aikaa, että se ratkaisee kokonaisajankulutuksen B:n eduksi.
B häviää kun kaikki syötteet ovat pieniä, mutta pienillä syötteillä kumpikin algoritmi kuluttaa aikaa niin vähän, että sillä ei yleensä ole merkitystä. Poikkeus tästä on, että jos algoritmia kutsutaan monta kertaa ja aina pienellä syötteellä, niin B on merkittävästi hitaampi.
Toisin kuin voisi luulla, tietokoneiden nopeuden kasvu yleensä lisää eikä vähennä niiden tilanteiden määrää, joissa kannattaa valita B, koska se kasvattaa sitä syötekokoa jonka kumpikin algoritmi ehtii käsitellä ennen kuin ajan kulutus käy liian suureksi.
Jos yhden ohjelman ajan kulutus on `20 n log n + 5` ja toisen `15 n log n + 5`, niin on selvää, että jälkimmäinen on nopeampi. Valitettavasti tilanne on erittäin harvoin näin selvä.
Ensiksi, ajan kulutus riippuu usein syötteen koon lisäksi syötteen laadusta. Esimerkiksi insertion-sort on melkein järjestyksessä olevalle isolle taulukolle paljon nopeampi kuin samankokoiselle täysin sekaisessa järjestyksessä olevalle taulukolle. Silloin tämän kaltainen lauseke pystyy esittämään ajan kulutuksen vain tietynlaisille syötteille. Usein ajan kulutus esitetään samankokoisista syötteistä sille, jolla aikaa kuluu eniten. Toisinaan esitetään samankokoisten syötteiden ajan kulutuksien keskiarvo.
Toiseksi, ajan kulutusta tarkasti kuvaava funktio on usein monimutkainen. Se voi olla esimerkiksi `8n^2 - 2 n |__log n__| + 12 n + 7`. Melkein aina on kuitenkin olemassa yksinkertainen funktio, joka tuottaa suurilla `n`:n arvoilla likimain samat tulokset. Tässä esimerkissä `8n^2` on sellainen funktio. Tällainen yksinkertainen funktio tuottaa yleensä riittävän tarkan tuloksen, koska ajan kulutusta suurilla syötteillä ei yleensä tarvitse tietää aivan tarkkaan, ja pienillä syötteillä riittää yleensä tieto että se on pieni.
Kolmanneksi, usein tiedämme esimerkiksi, että ajan kulutus suurilla syötteillä on likimain `c n log n`, missä `c` on jokin vakio, mutta emme yleensä tiedä `c`:n arvosta juuri mitään silloin kun tietoa tarvittaisiin. Se riippuu käytössä olevasta tietokoneesta, ohjelmointikielestä, kääntäjästä tai tulkista, käyttöjärjestelmän versiosta, algoritmin toteutuksen yksityiskohtien valinnasta, muista tietokoneessa samanaikaisesti suoritettavista ohjelmista ja mahdollisesti jopa akun varaustilasta.
Kun ohjelma on toteutettu, `c`:lle voidaan usein (mutta ei aina) saada hyvä likiarvo mittauksilla. Tämä on liian myöhään, jos olisimme halunneet tiedon sen päättämiseksi, mikä vaihtoehto kannattaa toteuttaa.
Käytännössä algoritmi pyritään toteuttamaan niin hyvin kuin kohtuullisella vaivalla onnistuu. Yleensä sillä tavalla tulee riittävän hyvä tulos, jos algoritmi on hyvin valittu. Jollei tule, aletaan etsiä keinoja nopeuttaa toteutusta tai muulla tavalla ratkaista ongelma.
Tilanne on toisenlainen silloin, kun verrattavana on kaksi algoritmia, joiden ajan kulutusten yksinkertaiset likimääräiset funktiot ovat eri muotoa. Olkoot ne esimerkiksi `c n^2` ja `d n log n`. Koska suoritusajat eivät voi olla nolla eivätkä negatiivisia, pätee `c > 0` ja `d > 0`. Ovatpa `c` ja `d` mitä tahansa positiivisia reaalilukuja, on vääjäämättä olemassa jokin luku, jota suuremmilla `n`:n arvoilla `d n log n``<``c n^2`. Mitä suurempi `d` on ja mitä pienempi `c` on, sitä suurempi pienin tällainen luku on. Käytännön tilanteissa pienin tällainen luku on melkein aina niin pieni, että sitä suuremmat syötteet ovat tavallisia. Tästä nyrkkisäännöstä on poikkeuksia, mutta ne ovat harvinaisia.
Tästä ei seuraa, että aina kannattaa valita algoritmi, jonka ajan kulutuksen muoto on paras. On esimerkiksi tavallista, että vaikka `c n` onkin muodoltaan parempi kuin `d n log n`, ero on isoillakin syötteillä niin pieni, että sillä ei ole merkitystä. Sen sijaan `c n^2` on yleensä isoilla syötteillä niin hidas, että paremman vaihtoehdon etsimiseen ja toteuttamiseen kannattaa panostaa. Oikea johtopäätös on, että ajan kulutuksen muotoon kannattaa kiinnittää paljon huomiota.
Edellä kerrotuista syistä algoritmien analyysissä riittää yleensä tunnistaa eniten merkitsevä termi, esimerkiksi `cn^2` tai `cn log n`, ja ilmoittaa se ilman vakiokerrointa `c`. Tähän käytetään O-, Ω- ja Θ-merkintöjä. Ne luetaan ”iso oo”, ”iso omega” ja ”iso theta”, koska myös ”pikku oo” ja "pikku omega” ovat käytössä samantapaisissa rooleissa. Tässä tehtävässä opiskelemme kolme ensin mainittua. Niiden merkitys on seuraava:
Muut merkinnät kuin Θ tarvitaan, koska ajan kulutuksen muotoa ei aina pystytä selvittämään tarkasti eikä välttämättä edes ole olemassa muotoa, joka pätisi kaikenlaisille syötteille. Esimerkiksi insertion-sortin ajan kulutus on melkein järjestyksessä oleville taulukoille muotoa `c n` ja tyypillisille taulukoille muotoa `c n^2`. Millekään taulukoille se ei ole parempi kuin `c n` eikä huonompi kuin `c n^2`. Siksi voidaan sanoa, että insertion-sortin ajan kulutus on `Omega(n)` ja `O(n^2)`, mutta ei voida sanoa, että se on `Theta(...)`, olipa kolmen pisteen paikalla mitä tahansa. Kuitenkin voidaan sanoa, että se on hitaimmillaan `Theta(n^2)` ja nopeimmillaan `Theta(n)`.
Jos `k > h`, niin `n^k` merkitsee enemmän kuin `n^h`. Termi `n` merkitsee enemmän kuin `sqrt n`, ja `sqrt n` merkitsee enemmän kuin `log n`.
Kirjoita sulkujen sisään mahdollisimman yksinkertainen lauseke siten, että väittämä pätee.
Mitkä seuraavista pätevät insertion-sortin suoritusajalle?
Mitkä seuraavista pätevät insertion-sortin hitaimman tapauksen suoritusajalle?
Mitkä seuraavista pätevät insertion-sortin nopeimman tapauksen suoritusajalle?
Tästä tärkeästä asiasta olisi paljon enemmänkin sanottavaa, mutta eiköhän tässä ollut riittävästi yhdelle kertaa.