Aikavaativuus määritellään tarkemmin luentomateriaalissa, joten tässä annamme ainoastaan heuristisen tavan ajatella aikavaativuutta. Aikavaativuuden tarkoitus on kuvata algoritmin nopeutta yksinkertaisella tavalla.
Seuraavan koodinpätkän kuvaama algoritmi selvittää, löytyykö taulukosta t lukua 0
for(int i=0; i<t.length; i++)
if(t[i]==0)
return true;
return false;
Intuitiivisesti on selvää, että algoritmin kuluttama aika riippuu lineaarisesti taulukon koosta n. Tämä tarkoittaa sitä, että esimerkiksi taulukon koon kaksinkertaistuessa algoritmin kuluttama aika suunnilleen kaksinkertaistuu. Tällaisessa tilanteessa sanomme, että algoritmin aikavaativuus on O(n).
Seuraava algoritmi tarkistaa, onko taulukossa kahta samaa lukua
for(int i=0; i<t.length; i++)
for(int j=0; j<t.length; j++)
if(t[i]==t[j] && i!=j)
return true;
return false;
Jälleen on intuitiivisesti selvää, että algoritmin kuluttama aika riippuu neliöllisesti taulukon koosta n, eli jos taulukon koko kaksinkertaistuu, niin algoritmin kuluttama aika likimain nelinkertaistuu. Tässä tilanteessa sanomme, että algoritmin aikavaativuus on O(n2). Saamme muutettua algoritmiamme nopeammaksi huomaamalla, että riittää tarkistaa vain tapaukset, jossa i<j. Tällöin koodi muuttuu muotoon
for(int i=0; i<t.length; i++)
for(int j=i+1; j<t.length; j++)
if(t[i]==t[j])
return true;
return false;
Tämänkin algoritmin aikavaativuus on O(n2). Tämä johtuu siitä, että tarkastettavia pareja on
n-1 + n-2 + ... + 1 = (n-1)(n-2)/2 = 0.5n2 - 1.5n + 1
Nyt termin 0.5n2 vaikutus isoilla n arvoilla on huomattavasti suurempi kuin muiden termien vaikutus, joten näiden termien vaikutus voidaan unohtaa. Lisäksi termin edestä unohdetaan vakiokerroin 0.5, sillä se ei kerro kiinnostavaa informaatiota ajankulutuksen käyttäytymisestä arvon n kasvaessa.
Esimerkiksi algoritmin
for(int i=0; i<n; i++)
//jotain vakiomäärän operaatioita vaativaa
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
//jotain vakiomäärän operaatioita vaativaa
aikavaativuus on O(n2) ja algoritmin
for(int i=0; i<n; i++)
for(int j=0; j<2*n; j++)
for(int k=0; k<3*n; k++)
//jotain vakiomäärän operaatioita vaativaa
aikavaativuus on O(n3).
Voidaankin hieman yksinkertaistetusti todeta, että aikavaativuus saadaan huomioimalla algoritmin ajankulutuksesta ainoastaan eniten vaikuttava osa kun n on suuri, ja siitäkin unohdetaan vakiokerroin edestä. Luentomateriaalissa esiintyvä formaali määritelmä perustuu tämän idean formalisointiin.
Joskus algoritmin aikavaativuus voi riippua useammasta kuin yhdestä tekijästä. Tällöin aikavaativuuden perusidea on sama kuin yhdenkin muuttujan tapauksessa. Esimerkiksi jos algoritmin pitää järjestää n pituinen taulukko (O(n logn) järjestysalgoritmia käytten) k kertaa, on tämän algoritmin aikavaativuus O(kn logn). Jos taas algoritmi käy läpi kahden taulukon alkiot, niin algoritmin aikavaativuus on O(n + m), missä n ja m ovat taulukoiden pituudet.
TMC-tehtävät on tarkoitus toteuttaa tehokkaasti, sillä jokaisessa tehtävässä vastaus tulee saada aikaiseksi yhden sekunnin sisällä. Tehtävän läpäisevän algoritmin aikavaativuuden voi usein päätellä syötteen koosta n, joka voi olla esimerkiksi syötteenä annetun taulukon tai merkkijonon pituus, tai jotain muuta. Esimerkiksi:
n=100000=105, niin tehtävässä haetaan algoritmia, jonka aikavaativuus on joko O(n) tai O(n log(n)).
n=1000=103, niin tehtävässä haetaan algoritmia, jonka aikavaativuus on noin O(n2).
n=100, niin tehtävässä haetaan algoritmia, jonka aikavaativuus on noin O(n3).
n=20, niin tehtävässä haetaan algoritmia, jonka aikavaativuus on noin O(2n).
10 ja erittäin harvoin yli 100, joten pelkästä aikavaativuudesta voi yleensä päätellä melko hyvin miten paljon algoritmisi kuluttaa aikaa.
Summataulukon toteuttaminen on viikon 1 tehtävänä 2.
Tarkastellaan seuraavaa ongelmaa. Syötteenä on annettu taulukko t ja tehtävänä on pystyä selvittämään nopeasti, kuinka paljon on taulukon indeksien l ja r välissä olevien lukujen summa eli t[l]+t[l+1]+...+t[r]. Samankaltaisiin kyselyihin on lisäksi pystyttävä vastaamaan useita kertoja. Kyselyyn voisi ratkaista suoraviivaisesti vain laskemalla joka kerta kyseisen summan alkio kerrallaan, mutta tämä on melko hidasta, varsinkin jos kyselyitä on useita samasta taulukosta.
Käyttämällä summataulukkoa yllämainittuihin kyselyihin voidaan vastata vakioajassa. Summataulukossa luodaan uusi taulukko s, jossa s[i]=t[0]+...+t[i]. Nyt summa t[l]+t[l+1]+...+t[r] voidaan laskea nopeasti taulukon s avulla, se on nimittäin s[r]-s[l-1] kun l>0 ja s[r] kun l=0.
Summataulukon rakentaminen onnistuu lineaarisessa ajassa syötteenä olevan taulukon pituuden suhteen. Tämä johtuu siitä, että s[0]=t[0] ja s[i+1]=s[i]+t[i+1].
Tarkastellaan summataulukon toimintaa esimerkin avulla. Olkoon meillä taulukko t, jossa on luvut
4, 1, 9, 2, 7, 3.Nyt taulukossa
s on luvut
4, 5, 14, 16, 23, 26.Jos halutaan laskea välin
[1,4] summa, joka siis on 1+9+2+7=19, saadaan se nopeammin taulukosta s laskemalla 23-4=19. Toisaalta jos halutaankin laskea välin [3,5] summa 2+7+3=12, saadaan se laskemalla 26-14=12. Esimerkkinä erikoistapauksesta, jossa väli alkaa nollasta, on välin [0,3] summa 4+1+9+2=16 valmiina jo tallennettuna taulukon s indeksiin 3.
Binäärihaku saattaa olla tuttu jo aiemmilta kursseilta, mutta todennäköisesti ainoastaan yhteydessä, jossa etsitään jotain lukua järjestyksessä olevasta taulukosta. Sitä voi kuitenkin käyttää huomattavasti yleisemminkin algoritmisessa ongelmanratkaisussa.
Varsin usein algoritmiset kysymykset ovat muotoa "etsi suurin sellainen x, jolla ehto P(x) pätee", missä x voi saada arvoja joltain väliltä, esimerkiksi [0,N]. Tällöin ehdon P(x) toteutumisen tarkastaminen voi olla paljon helpommin lähestyttävävissä oleva ongelma, kuin pienimmän x, jolle kyseinen ehto pätee, löytäminen. Yksi tapa ratkaista tehtävä olisi yksinkertaisesti käydä läpi kaikki luvut 0..N ja tarkastaa ehdon täyttyminen jokaisella luvulla erikseen. Tällöin ehdon P(x) toteutuminen tarkastettava N+1 kertaa, joka voi viedä erittäin paljon aikaa luvun N ollessa suuri.
Jos ehto P(x) kuitenkin toteuttaa vielä yhden lisäehdon, voidaan tehtävä ratkaista huomattavasti nopeammin. Jos nimittäin P(x) täyttyy ensin kaikilla luvuilla [0,k] eikä sen jälkeen enää täyty yhdelläkään luvulla väliltä [k+1,N], niin luku k voidaan binäärihakea.
Haku etenee seuraavalla tavalla: oletetaan, että luvun k tiedetään olevan välillä [a,l], olkoon m=(a+l+1)/2. Jos P(m) pätee, niin k on välillä [m,l]. Jos taas P(m) ei päde, niin k on välillä [a,m-1]. Kummassakin tapauksessa sen välin pituus, johon k kuuluu, puolittuu (ainakin melkein). Täten jos aloitamme välistä [0,N], niin ehto P joudutaan tarkistamaan noin log2N kertaa, mikä on huomattava parannus aiempaan verrattuna.
Lisämateriaalia binäärihausta löydät mm. kisakoodarin käsikirjasta, jossa sille on omistettu kokonainen luku. Lisämateriaali ei kuitenkaan ole pakollinen tämän viikon tehtävien ratkaisemiseksi.