Onko algoritmien vaativuuden luokittelu vaativuusluokkiin
perustuen mielekäs?
• Kuten pian näemme, äsken esitelty lisäysjärjestäminen toimii pahimmassa
tapauksessa neliöllisesti eli ajassa T(n) = O(n
2)
• Kurssin aikana tutustumme muutamiin pahimmassa tapauksessa ajassa
T(n) = O(n log n) toimiviin järjestämisalgoritmeihin (lomitus- ja
kekojärjestäminen)
• Vaativuusluokka siis "unohtaa" kertoimet algoritmin vaativuutta kuvaavasta
funktiosta. Onko näin saatu luokittelu mielekäs?
• Oletetaan, että lisäysjärjestäminen on toteutettu erittäin optimaalisesti ja sen
tarkkaa suoritusaikaa kuvaa funktio Tlis(n) = 2n
2
, eli vakiokerroin olisi vain 2
• Oletetaan lisäksi, että aloitteleva ohjelmoija on toteuttanut ajassa O(n log n)
toimivan lomitusjärjestämisen melko epäoptimaalisesti, ja toteutuksen
tarkkaa suoritusaikaa kuvaa funktio Tlom(n) = 50n log2 n
• Jos syöte on pienehkö (luokkaa n<200), toimii lisäysjärjestäminen
nopeammin
• Koska nykyiset tietokoneet ovat erittäin nopeita, ei pienen syötteen (n<200)
suoritusajalla ole merkitystä edes huonosti toteutetulla algoritmilla
57
• Entä isot syötteet? Oletetaan, että järjestettävänä on 10 miljoonan kokoinen
taulukko
• Oletetaan, että lisäysjärjestäminen suoritetaan koneella NOPEA, joka
suorittaa 109 komentoa sekunnissa
• Oletetaan lisäksi, että lomitusjärjestäminen suoritetaan koneella HIDAS, joka
suorittaa ainoastaan 106 komentoa sekunnissa. NOPEA on siis 1000 kertaa
nopeampi kone kuin HIDAS
• Nyt kone NOPEA järjestää hyvin toteutetulla O(n
2) ajassa voimivalla
lisäysjärjestämisellä luvut 200000 sekunnissa eli reilussa 55 tunnissa
Tuhat kertaa hitaampi kone HIDAS järjestää epäoptimaalisesti toteutetulla,
mutta ajassa O(n log n) toimivalla lomitusjärjestämisellä noin 11627
sekunnissa, eli alle 3,3:ssa tunnissa
• Eli kuten huomaamme, suurilla syötteillä kahden vaativuusluokan välillä on
ratkaiseva ero vakiokertoimista huolimatta