ALGORITMIEN SUUNNITTELU JA ANALYYSI

Kevät-2007

Harjoitus 3.

1. Ratkaise

ì 2, kun n = 1

T(n) = í

î 2T(n - 1) + 1, kun n ≥ 2

purkamalla yhtälö. Tarkista ratkaisusi vielä induktiolla.

2. Määrää seuraavien palautuskaavojen ratkaisuille O-ylärajat. Kaikissa tapauksissa T(1) = 1 ja funktioita tarkastellaan vain, kun n on kahden potenssi.

a) T(n) = T(n/2) + 1

b) T(n) = 2T(n/2) + n³

c) T(n) = 2T(n/2) + n²

3. a) Osoita, että pikajärjestämisalgoritmi (quicksort) vaatii pahimmassa tapauksessa ajan O(n²) .

b) Osoita, että pikajärjestämisalgoritmi vaatii pahimmassa tapauksessa ajan W( n²).

Näistä seuraa, että pahimman tapauksen aikavaatimus on Q(n²).

4. Taulukko A[1..n] sisältää kaikki kokonaisluvut 0..n yhtä lukuunottamatta. Kirjoita pseudokoodi mahdollisimman tehokkaalle algoritmille, joka selvittää puuttuvan luvun. Vihje: apuna voi käyttää esim. toista taulukkoa B[0..n]. Laske algoritmisi aikavaatimus.

5. Jonoon on toteutettu operaatiot put(x), joka lisää alkion jonon loppuun (O(1), kun pidetään tallessa osoitinta jonon loppuun), ja multiget(k), joka poistaa jonon alusta k alkiota kerralla (jos jonossa on alle k alkiota, operaatio tyhjentää sen). Analysoi näiden operaatioiden tasoitettu aikavaatimus.

6. Dynaaminen taulukko on toteutettu siten, että taulukon ollessa täysi lisäysoperaatio varaa uuden kooltaan kaksinkertaisen taulukon, kopioi vanhan taulukon sisällön uuteen ja lisää uuden alkion uuteen taulukkoon. Lisäysoperaatio on siis luennoilla esitetyn kaltainen. Poisto-operaatio on toteutettu lisäysoperaation käänteisoperaationa: jos alkion poiston jälkeen taulukossa on vain puolet paikoista varattu, operaatio varaa uuden taulukon, kooltaan puolet vanhasta, ja kopioi vanhan taulukon sisällön uuteen. Alkion lisääminen ja poistaminen ilman kopiointia vaativat ajan O(1) ja yhden alkion kopiointi ajan O(1). Rakenteeseen kohdistetaan jono lisäyksiä ja poistoja. Analysoi operaatioiden tasoitettu aikavaatimus.