Tehtävä:
Isot O, Ω ja Θ

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 valinta­tilannetta, 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 melko tarkasti lauseketta `n^2/50` paitsi hyvin pienillä `n`. (Yksi sekunti on 1000 millisekuntia.) Algoritmi B on monimutkainen ja vaikea ohjelmoida. Sen millisekunteina mitattu ajan kulutus syötteen koon `n` funktiona noudattaa melko tarkasti lauseketta `n log n` paitsi hyvin pienillä `n`.

Nappia klikkaamalla saat näkyviin A:n ajan kulutuksen kuvaajan vihreällä ja B:n punaisella. Kirjaimen `n` sijaan kuvaajassa joudutaan käyttämään kirjainta `x`, koska MathCheck ei suostu piirtämään käyriä muuttujalle, joka edustaa kokonaislukua. Täytyy siis ajatella, että käyrän `x` tarkoittaa syötekokoa `n`. MathCheck piirtää kuvaajan alkaen `x`:n eli `n`:n arvosta 0 siihen arvoon saakka, jonka kirjoitat keskimmäiseen laatikkoon.

tai

Valitse oikeat vaihtoehdot.
Syötteen koko voi olla vain luonnollinen luku, mutta käyrät käyttävät `n`:n arvoina muitakin lukuja.
Hyvin pienillä `n` A on hitaampi kuin B.
Käyrien mukaan hyvin pienillä `n` A on hitaampi kuin B, mutta se ei ole todellinen ilmiö vaan johtuu siitä, että lausekkeet tuottavat likiarvoja.
Keskisuurilla `n` A on nopeampi ja suurilla hitaampi kuin B.
Kaikilla niillä syötteen arvoilla, joilla jompikumpi algoritmi kuluttaa aikaa enintään sekunnin, A on nopeampi kuin B.
tai

Kirjoita taulukkoon A:n ja B:n ajan kulutus annetuilla `n`:n arvoilla.
`n`110100100010000
A
B
tai

Taulukon täsmälleen yhden ruudun lukema on mahdoton ajan kulutukseksi. Se on rivillä (vastaa A tai B) sarakkeessa (vastaa 1, 10, … tai 10000) .
tai

Kumpi algoritmi kannattaa valita seuraavissa tilanteissa? Vastaa A tai B.

Algoritmia tullaan käyttämään samassa ohjelmassa sata kertaa. Yhdellä kertaa syöte­koko on 1000 ja muilla kerroilla 10.
tai
Algoritmia ajetaan hyvin monta kertaa, ja suurin koskaan esiintyvä syöte on kooltaan enintään 100.
tai
Kännykän käyttäjä malttaa odottaa vastausta korkein­taan 0,5 sekuntia. Laskentaan menee tämän algoritmin käyttämän ajan lisäksi 0,4 sekuntia muuhun.
tai
Seuraavassa käyttöjärjestelmäversiossa muun laskennan aika saatiin nopeutettua 0,2 sekuntiin. Muuten tilanne on sama kuin edellä.
tai
Algoritmi sijoitetaan yleis­käyttöiseen kirjastoon. Sen käytössä esiintyvistä syöte­koista ei tiedetä mitään.
tai

Vastauksen on tultava 3 sekunnissa. Suurin syöte­koko, josta A selviää siinä ajassa, on . Suurin syöte­koko, josta B selviää siinä ajassa, on .
tai

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öte­kokoja koskeva tieto on puutteellista. Yksikin iso syöte saattaa viedä A:lla niin paljon aikaa, että se ratkaisee kokonais­ajan­kulutuksen 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: 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öte­kokoa jonka kumpikin algoritmi ehtii käsitellä ennen kuin ajan kulutus käy liian suureksi.


Jos yhden ohjelman ajan kulutus on likimain `20 n log n` ja toisen `15 n log n`, niin jälkimmäinen on nopeampi. Valitet­tavasti vaikka tietäisimme, että ajan kulutus on likimain `c n log n`, missä `c` on vakio, emme yleensä tiedä `c`:n arvosta juuri mitään silloin kun tietoa tarvittaisiin. Se riippuu käytössä olevasta tieto­koneesta, ohjelmointi­kielestä, kääntäjästä tai tulkista, käyttö­järjestelmän versiosta, algoritmin toteutuksen yksityis­kohtien valin­nasta, muista tieto­koneessa saman­aikaisesti suoritet­tavista ohjelmista, syötteen laadusta (melkein järjes­tyksessä oleva taulukko on helpompi saada täysin järjestykseen kuin täysin sekaisessa järjestyksessä oleva taulukko) ja mahdollisesti jopa akun varaustilasta.

Kun ohjelma on toteutettu, `c`:lle voidaan usein (mutta ei aina) saada hyvä likiarvo mittauksilla, mutta 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 funktiot ovat eri muotoa. Olkoot nämä funktiot 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 tämä luku on. Käytännön tilanteissa tämä luku on melkein aina niin pieni, että sitä suuremmat syötteet ovat tavallisia. Tästä nyrkki­sää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.

Ajan kulutus on harvoin niin yksinkertaista muotoa kuin edellä olleissa esimerkeissä. Tyypillisiä tarkempia muotoja ovat esimerkiksi `an^2 + bn + c` ja `an log n + bn + c`. Onneksi samasta syystä kuin tarpeeksi isoilla syötteillä `d n log n``<``c n^2`, tarpeeksi isoilla syötteillä `an^2` ja `an log n` ovat niin paljon isompia kuin `|bn+c|`, että termejä `bn` ja `c` ei tarvitse ottaa huomioon. Tässä vertailun kohteena oli `|bn+c|` vertailun mielekkyyden varmistamiseksi myös silloin, kun `b` on negatiivinen. Käytännössä `b` todella on toisinaan negatiivinen.

Siksi algoritmien analyysissä yleensä riittää tunnistaa eniten merkitsevä termi, esimerkiksi `an^2` tai `an log n`, ja ilmoittaa se ilman vakiokerrointa `a`. 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ä saman­tapaisissa 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 kaiken­laisille 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.

`7 n log n + 2 n^2 - 5n + 3 = Theta(``)`
tai
`32 n + 7 n log n - 12 sqrt(n) + 31 = Theta(``)`
tai
`7n(log n + 3 sqrt(n)) + 18 = Theta(``)`
tai
`25 + (n+4)^2 + 8log n - n^2 = Theta(``)`
tai

Mitkä seuraavista pätevät insertion-sortin suoritusajalle?
 `O(log n)`  `O(n)`   `O(n sqrt(n))`  `O(n^2)`   `O(n^3)` 
tai
 `Omega(log n)`  `Omega(n)`   `Omega(n sqrt(n))`  `Omega(n^2)`   `Omega(n^3)` 
tai
 `Theta(log n)`  `Theta(n)`   `Theta(n sqrt(n))`  `Theta(n^2)`   `Theta(n^3)` 
tai

Mitkä seuraavista pätevät insertion-sortin hitaimman tapauksen suoritusajalle?
 `O(log n)`  `O(n)`   `O(n sqrt(n))`  `O(n^2)`   `O(n^3)` 
tai
 `Omega(log n)`  `Omega(n)`   `Omega(n sqrt(n))`  `Omega(n^2)`   `Omega(n^3)` 
tai
 `Theta(log n)`  `Theta(n)`   `Theta(n sqrt(n))`  `Theta(n^2)`   `Theta(n^3)` 
tai

Mitkä seuraavista pätevät insertion-sortin nopeimman tapauksen suoritusajalle?
 `O(log n)`  `O(n)`   `O(n sqrt(n))`  `O(n^2)`   `O(n^3)` 
tai
 `Omega(log n)`  `Omega(n)`   `Omega(n sqrt(n))`  `Omega(n^2)`   `Omega(n^3)` 
tai
 `Theta(log n)`  `Theta(n)`   `Theta(n sqrt(n))`  `Theta(n^2)`   `Theta(n^3)` 
tai

Tästä tärkeästä asiasta olisi paljon enemmänkin sanottavaa, mutta eiköhän tässä ollut riittävästi yhdelle kertaa.