| Mikroautokisa | Algoritmien tehokkuus |
| Pelin mikroautoissa käytetään pieniä paristoja, joiden teho usein hiipuu kuljetun matkan pidentyessä. Hidastuminen ei välttämättä ole suoraan verrannollista matkan pituuteen nähden, vaan paristo voi heiketä huomattavasti nopeamminkin käytetyistä valmistustekniikoista johtuen. | Useimpien algoritmien suoritus hidastuu sitä mukaa, kun niiden käsittelemän syötteen koko kasvaa. Hidastuminen ei välttämättä ole suoraan verrannollista syötteen kokoon nähden, esimerkiksi 1000 luvun järjestäminen on käytännössä aina yli kymmenen kertaa hitaampaa kuin 100 luvun järjestäminen. |
| Laadukkailla paristontuottajilla on pienet toleranssit, ja paristojen tehon heikkeneminen ilmaistaan tarkkojen funktioiden avulla. Funktio voisi olla esimerkiksi 5n + 2*lg(n) + 30. Tällöin ajankulutus ensimmäisellä metrillä on 37 yksikköä, ja kun matkaa on kuljettu 10 metriä ajankulutus on kasvanut 86 yksikköön. | Algoritmin suoritukseen vaadittavien konekäskyjen määrä voidaan tarvittaessa laskea tarkkaan. Tällöin saadaan hyvä arvio suoritusajasta, kun kerrotaan keskimääräisen konekäskyn kuluttama aika käskyjen määrällä. |
| Kaikki paristontuottajat eivät kuitenkaan tee näin tarkkaa työtä. Osa esittää paristojen tehon heikkenemisen ainoastaan kertaluokan tarkkuudella. Jos pariston hidastuvuuden tiedetään olevan Θ(n), todellinen funktio voi olla esimerkiksi 2n, 5n + 2*lg(n) + 30 tai 42n + 7. | Yleensä ei kuitenkaan kannata laskea konekäskyjen määrää tarkkaan, useinmiten pelkkä pelkkä kertaluokka riittää. Tällöin tarkasta suoritusajan funktiosta syötekoon suhteen abstrahoidaan pois alemman asteen termit ja korkeimman asteen termin kerroin. Funktion kertaluokkaa esitetään tässä tapauksessa merkinnällä Θ( korkein_aste ), esim. Θ(n). |
| Joissakin paristoissa toleranssit ovat hyvin suuret, joukkoon mahtuu sekä hyviä että huonoja, mutta huonoimman mahdollisen pariston kertaluokka tiedetään. Se ilmoitetaan merkinnällä O( korkein_aste ). Jos pariston heikkemisen kertaluokka on O(n lg(n)), voi paristo todellisuudessa heiketä esimerkiksi funktioiden 2 * n lg(n) + 5, 4n + 8 tai 24 mukaisesti. | Kaikkien algoritmien kohdalla ei ole mahdollista käyttää Θ-merkintää, koska huonoimman ja parhaan tapauksen suoritusajat ovat eri kertaluokissa. Huonoimman tapauksen suoritusajan ilmaisemiseen voidaan käyttää ylärajaa O. Jos algoritmin suoritusaika on esimerkiksi O(n), tiedetään että kaikkien tapausten suoritusajat syötteestä riippumatta ovat korkeintaan vakiokertoimen päässä funktiosta n tai parempia. |
| Mukaan mahtuu myös paristoja tehtailta, joissa panostetaan enemmän määrään kuin laatuun: niistä tiedetään ainoastaan, että ne eivät missään tapauksessa ole tätä paremmassa kertaluokassa. Sen merkitsemiseen voidaan käyttää merkintää Ω( aste ). Jos pariston heikkemisen kertaluokka on Ω(n), voi paristo todellisuudessa heiketä esimerkiksi funktioiden 2 * n lg(n) + 5, 4n + 8 tai 10 n lg(n) + 15n + 27 mukaisesti. | Parhaimman tapauksen suoritusajan ilmaisemiseen voidaan puolestaan käyttää alarajaa Ω. Jos algoritmin suoritusaika on esimerkiksi Ω(n), tiedetään että kaikkien tapausten suoritusajat syötteestä riippumatta ovat korkeintaan vakiokertoimen päässä funktiosta n tai huonompia. |
| Kisojen pituudet vaihtelevat yhden ja kolmen kierroksen välillä. Pitkissä kisoissa hyvän kertaluokan paristot ovat tyypillisesti vahvoilla kun taas lyhyissä kisoissa matalasta vakiokertoimesta voi olla arvaamatonta apua. | Kertaluokat tarjoavat hyviä arvioita ainoastaan riittävän suurilla syötteillä. Pienillä syötteillä lähes mikä tahansa algoritmi on tarpeeksi hyvä, ja saattaa jopa olla kannattavaa valita kertaluokaltaan huonompi algoritmi, jonka vakiokerroin on pieni. |
