Tehtävä:
Sarjalle Θ-merkintä helposti

Lyhyt MathCheck-ohje (uuteen välilehteen)

Algoritmien suorituskyvyn analyysissa tulee usein lasket­tavaksi muotoa `f(0) + f(1) + ... + f(n)` olevan sarjan summa, missä `0 <= f(0)` ja `f(x) <= f(y)` aina kun `0 <= x <= y <= n`. Sarjan alku­kohta voi olla myös esimer­kiksi `1` ja loppu­kohta esimer­kiksi `n-1`. Joskus summan tarkka arvo on helppo laskea, mutta usein se on toivottoman vaikeaa. Algoritmien analyysissa ei kuitenkaan tarvita tarkkaa arvoa, vaan `Theta`-merkinnän tarkkuus riittää. Tässä tehtävässä opette­lemme helpon kikan, joka toimii melkein (mutta ei aivan) aina ja joka tuottaa vastauksen sillä tarkkuudella.

Pohtikaamme aluksi hetki, miksi juuri tuon muotoiset sarjat ovat yleisiä. Usein algoritmissa on silmukka, joka käsittelee taulukon tms. osaa, joka kasvaa kierros kierrokselta. Esimerkiksi insertion-sortin pää­silmukassa sijoitetaan alkio paikalleen osa­taulukkoon, jonka koko on ensimmäisellä kierroksella 1, toisella kierroksella 2 ja niin edelleen, kunnes se on viimeisellä kierroksella yhtä pienempi kuin `n` eli koko taulukon koko. Osa­taulukkoa selataan lopusta alkaen ja sen alkioita siirretään yksi askel oikealle, kunnes uuden alkion paikka on löytynyt. Huonoimmassa tapauksessa joudutaan selaamaan koko osa­taulukko. Huonoimman tapauksen työ­määrä on siis yksittäisellä kierroksella suoraan verrannollinen osa­taulukon kokoon ja yhteensä suoraan verrannollinen käsiteltävien osa­taulukoiden kokojen summaan eli lukuun `1 + 2 + ... + (n-1)`.

Koska ajan ja muistin kulutus eivät voi olla negatiivisia, voimme olettaa, että `f(0) >= 0`. Toisinaan tämä ehto rikkoutuu näennäisesti. On esimerkiksi varsin tavallista, että silmukan yhdellä kierroksella tehtävä työmäärä on `Theta(log n)`. Jos ensimmäisellä kierroksella käsitellään tyhjää tieto­rakennetta, sarja alkaa `log 0 + ...` eli ensimmäinen termi on `-oo`. Tällöin ensimmäinen termi ei kuitenkaan kuvasta todellista työmäärää. `Theta`-merkinnän määritelmä sallii ensimmäisen ja toisen termin (itse asiassa minkä tahansa kiinteän määrän termejä) olla mitä tahansa; vaaditaan ainoastaan, että on olemassa jokin raja, josta alkaen termit kuvaavat kasvu­vauhtia oikein. Tästä syystä ensimmäinen termi saattaa olla ihan humpuukia.

Toisaalta samasta syystä `Theta`-merkinnän määritelmä sallii jättää sarjamme alusta yhden tai kaksi termiä pois. Niinpä, jos `f(0) >= 0` tai `f(1) >= 0` ei päde, on luvallista aloittaa sarja termistä `f(1)` tai `f(2)`.

Koska silmukan käsittelemä tietorakenne tyypillisesti kasvaa kierros kierrokselta, ja koska isomman tieto­rakenteen käsittelyyn menee tyypillisesti enemmän aikaa kuin pienemmän, `f(0) <= f(1) <= ... <= f(n)` pätee tyypillisesti. Tulemme tarvitsemaan hieman vahvempaa oletusta

`f(0/2) <= f(1/2) <= ... <= f((2n)/2)`.

Tämä oletus on kuitenkin kömpelöä muotoa. Suoritus­aikaa kuvaamaan käytetyt funktiot noudattavat yleensä yksin­kertaisempaa, vielä vahvempaa oletusta: ne ovat kasvavia reaali­luku­välillä `0 <= x <= n`. Alussa annettu oletus sanoo juuri tämän. Jos sarja aloitetaankin `f(1)`:stä, riittää kasvavuus välillä `1 <= x <= n`.

Tarkasteltava sarja ei kuitenkaan aina ole todellisesta algoritmista peräisin, ja algoritmeissakin saattaa esiintyä poikkeuksia. Siksi on syytä aina aloittaa varmis­tautu­malla, että ehdot todellakin pätevät, kenties sen jälkeen kun alusta on jätetty yksi tai kaksi termiä pois.

Pätevätkö ehdot seuraaville sarjoille?

`0^2 + 1^2 + 2^2 + ... + n^2`
Ehdot pätevät.
Ehdot eivät päde, mutta astuvat voimaan jättämällä alusta enintään kaksi termiä pois.
Kumpikaan edellisistä ei päde.
tai

`(0+(-1)^0) + (1+(-1)^1) + ... + (n+(-1)^n)`
Ehdot pätevät.
Ehdot eivät päde, mutta astuvat voimaan jättämällä alusta enintään kaksi termiä pois.
Kumpikaan edellisistä ei päde.
tai

`1 sqrt(-1) + 3 sqrt(0) + ... + (2n+1)sqrt(n-1)`
Ehdot pätevät.
Ehdot eivät päde, mutta astuvat voimaan jättämällä alusta enintään kaksi termiä pois.
Kumpikaan edellisistä ei päde.
tai

Tämän tehtävän kikassa muodostetaan sarjan summalle hyvin yksin­kertainen ylä­liki­arvo ja sievennetään se mahdol­lisimman yksin­kertaiseen `O`-muotoon. Sitten muodostetaan yksin­kertainen ala­liki­arvo ja sievennetään se mahdol­lisimman yksin­kertaiseen `Omega`-muotoon. Lopuksi katsotaan, tuliko samat muodot. Jos tuli samat, tulos on sarjan summalle pätevä `Theta`-merkintä. Jollei tullut samat, menetelmä epä­onnistui. Yleensä tulee samat.

Ylä­liki­arvo muodostetaan kertomalla sarjan viimeinen termi sarjan termien määrällä. Tämä on ylä­liki­arvo sarjan summalle, koska kasvavuus­oletuksen vuoksi viimeinen termi on ylä­liki­arvo mille tahansa termille. Tee tämä sarjalle `1^2 + 2^2 + ... + n^2`! Kertolaskun tarkka tulos on , joka on `O(``)`.
tai

Sarjan summalle saataisiin ala­liki­arvo kertomalla ensim­mäinen termi termien määrällä, mutta se on yleensä eri muotoa kuin ylä­liki­arvo, joten näin menetellen ei päästä tavoitteeseen. Melkein aina tavoit­teeseen vievä ala­liki­arvo saadaan käyttämällä keskim­mäistä termiä ala­liki­arvona sarjan loppu­osan jokaiselle termille ja jättämällä alku­osan termit pois. Keskim­mäinen termi on kasvavuus­oletuksen vuoksi pätevä ala­likiarvo loppu­osan termeille. Lupa jättää alku­osan termit pois tulee siitä, että ne ovat oletuksen mukaan ei-negatiivisia. Toisin sanoen, niille käytetään ala­liki­arvona nollaa.

Tarkastellaan ensin tilannetta, jossa ensimmäinen termi on `f(1)` ja viimeinen `f(n)`. Jos termejä on pariton määrä, keskimmäinen termi on `f((n+1)/2)` ja siitä alkavassa loppu­osassa on `(n+1)/2` termiä. Jälkimmäistä voidaan arvioida alas­päin lausekkeella `n/2`, ja kasva­vuuden ansiosta edellistä voidaan arvioida alas­päin lausekkeella `f(n/2)`. Näin saadaan ala­liki­arvo `n/2 f(n/2)`, joka on helpompaa muotoa kuin muut vaihto­ehdot.

Jos termejä on parillinen määrä, keski­kohta osuu termien `f(n/2)` ja `f(n/2+1)` väliin. Riippuen siitä, kumpi niistä valitaan, loppu­osan termien määräksi saadaan `n/2+1` tai `n/2`. Jos valitaan ensimmäinen keski­kohta mutta otetaan huomioon vain `n/2` viimeistä termiä, ala­liki­arvoksi saadaan sama helppo lauseke `n/2 f(n/2)` kuin edellä. Sitä voidaan siis käyttää aina, riippumatta siitä, onko `n` parillinen vai pariton.

Jos ensimmäinen termi onkin `f(0)`, voimme silti käyttää lauseketta `n/2 f(n/2)`, koska oletuksen mukaan `f(0) >= 0`, joten summa on enintään `0 + n/2 f(n/2)`.

Tällä keinolla sarjan `1^2 + 2^2 + ... + n^2` summalle saadaan ala­liki­arvo . Kun vakiot siirretään eteen, saadaan `= Omega`().
tai

Saimme saman­muotoiset `O`- ja `Omega`-merkinnät, joten sarjan `1^2 + 2^2 + ... + n^2` summa on `Theta(``)`.
tai

Otetaan seuraavaksi `log 1 + ... + log n`. Valitse.
Olen tarkastanut, että ensimmäinen termi on vähintään 0.
Olen tarkastanut, että `log(x)` on kasvava välillä `1 <= x <= n`.
Sitoudun noudattamaan kilometrin mittaista käyttö­sopimusta, joka on niin kömpelöä laki­tekstiä, että siitä ei saa kukaan selvää.
Lupaan olla kiltti kansalainen, syödä terveellisesti ja opiskella ahkerasti.
tai

Sarjan summan ylä­liki­arvoksi tulee , joka on `O(``)`.
tai

Sarjan summan ala­liki­arvoksi tulee
.
Koska riittää ottaa huomioon eniten merkitsevä termi, summa on `Omega(``)`.
tai

Niinpä `log 1 + ... + log n = Theta(` `)`.
tai

Entä jos pitääkin laskea `log 1 + ... + log (n-1)`? Sehän on `(log 1 + ... + log n) - log n`, missä sulkujen sisältö tutkittiin edellä. Edellä saatu vastaus on enemmän merkitsevää muotoa kuin `log n`, joten `-log n` voidaan jättää pois. Saadaan siis sama vastaus kuin edellä. Helppoa! Muista kuitenkin, että vähemmän merkitsevän termin saa jättää pois vain kiinteän määrän kertoja. On oikein päätellä, että koska `log 1` ja `log 2` ovat vakioita ja siksi merkitsevät vähemmän kuin `log n`, ne saa jättää pois ja siis
`Theta(log 1 + ... + log n) = Theta(log 3 + ... + log n)`.
Ei kuitenkaan olisi oikein toistaa tämä päättely kolmen pisteen yli ja todeta, että
`Theta(log 1 + ... + log n) color(red)(= Theta(log n))`.

Käsitellään seuraavaksi hieman hankalampi tapaus:
`5 sqrt(1) + 7 sqrt(2) + ... + (2n-1)sqrt(n-2)`.
Koska haluamme aina lopulta mahdollisimman yksin­kertaisen muodon, valitsemme indeksoinnin siten, että neliö­juuren alle tulee indeksi sellaisenaan. Tähän pääs­tään, kun valitaan `f(i) =`. Silloin pienim­mäksi indeksiksi tulee ja suurim­maksi .
tai

Jotta sarjan viimeisessä termissä olisi neliö­juuren alla vain `n`, lisäämme sarjan loppuun
.
Ratkaisemme siis eri sarjaa kuin alun perin tehtäväksi saimme. Toiveenamme on, että lopuksi voimme jättää nyt lisätyn pois sillä perusteella, että se on vähemmän merkitsevää muotoa kuin saatu sarjan summa. Jos niin käy, niin muuntamamme sarjan ratkaisu pätee myös alku­peräiselle.
tai

Tästä eteenpäin tarkastellaan sarjaa, johon ym. termit on lisätty, kunnes toisin sanotaan.
Olen tarkastanut, että ensimmäinen termi on vähintään 0.
Olen tarkastanut, että `f(x)` on kasvava sillä välillä jota nyt käytetään.
tai

Äskeisellä reseptillä ylä­liki­arvoksi saadaan
`= O(``)`.
tai

Äskeisellä reseptillä ala­liki­arvoksi saadaan
`= Omega(``)`.
tai

Molemmista tuli sama muoto, ja se on merkitsevämpi kuin se mikä edellä lisättiin. Niinpä edellä lisätyt voi poistaa muodon muuttumatta. Kaikkiaan saimme tulokseksi `5 sqrt(1) + 7 sqrt(2) + ... + (2n-1)sqrt(n-2) =`
`Theta(``)`.
tai

Otetaan lopuksi tapaus, jossa kikka ei toimi: `4^1 + 4^2 + ... + 4^n`. Äskeisellä reseptillä ylä­liki­arvoksi saadaan
`= O(``)`.
tai

Äskeisellä reseptillä ala­liki­arvoksi saadaan
`= Omega(``)`.
tai

Ne eivät ole samaa muotoa. Potenssi­laskun kanta­luku ei ole vakio­kerroin, jonka saa poistaa tai vaihtaa ykköseksi `Theta`-merkintää käytettäessä. (Jos saisi, voisimme johtaa `2^n color(red)(= Theta(1^n) = Theta(1))` eli varsin nopeasti kasvava funktio olisi samaa muotoa kuin funktio, joka ei kasva lainkaan!)

Saamme laskettua tämän summan tarkasti tekemällä siitä yhtälön. Merkitsemme `x = 4^1 + 4^2 + ... + 4^n`. Kertomalla molemmat puolet 4:llä saadaan
`=``+ ... +`.
tai

Vähentämällä tästä `x = 4^1 + ... + 4^n` (siis vasemmalta puolelta vähennetään `x` ja oikealta `4^1 + ... + 4^n`) saadaan
`=`
tai

Niinpä `x =``= Theta(``)`.
tai

Tarkan muodon vertaaminen edellä johdettuihin ylä- ja ala­liki­arvoihin kertoo, että kumpikin liki­arvo on huono. Tässä tapauksessa syynä on se, että sarjan termit kasvavat varsin nopeasti. Tällaisia sarjoja esiintyy algoritmien analyysissa, mutta silloin algoritmi on ainakin joillakin suurilla syötteillä toivottoman hidas. Yleensä pyritään löytämään nopeampia algoritmeja jos mahdol­lista. Siksi tämän tehtävän kikka toimii käytännön algoritmien analyysissa melkein aina.

Edellä käytetty ylä­liki­arvon muodostamis­tapa on hyvin yksin­kertainen. Ala­liki­arvon muodostamis­tapa kannattaa muistaa, sillä se on laajasti käyttö­kelpoinen. Se oli seuraava:

  1. Sarja jaettiin kahtia pieniin ja suuriin termeihin.
  2. Jokaisen pienen termin ala­liki­arvona käytetttiin nollaa.
  3. Jokaisen suuren termin ala­liki­arvona käytetttiin keskimmäistä termiä.