Tietorakenteet / syksy 2009 / Linna

Harjoitus 1, viikko 37

1. Ns. Cocktailsekoitinlajittelu (cocktail shaker sort) on kuplalajittelun muunnos, jossa taulukkoa käydään läpi vuorotellen alusta loppuun ja lopusta alkuun. Joka toisella kierroksella kuplat nousevat pintaan ja paluukierroksella painavat alkiot painuvat pohjaan. esitä kyseinen lajittelualgoritmi.

2. Määritä seuraavien funktioiden suuruusluokka. Toisin sanoen etsi jokaiselle funktiolle f mahdollisimman yksinkertainen funktio g siten, että f on O(g).

a) n³ + 3n b) log(n⁴) c) nlogn + 5(log(n))³ d) log(3ⁿ).

3. Määritä n:n funktiona seuraavien lausejonojen suoritusajan suuruusluokka.

a) for (i =0; i <n; i ++)

for (j=0; j< i; j++)

for (k=0; k<j; k++)

x=x+1;

b) i =1;

while (i <= n) {

x =x+1;

i = i +1;

}

4. Määritä n:n funktiona (tarkka lauseke) kuinka monta kertaa seuraavassa lausejonossa suoritetaan sijoituslause x = x+1 ? Määritä sen jälkeen saadun lausekkeen suuruusluokka.

for (i=1; i<n; i=i+2)

for (j=1; j<=i; j++)

for (k=1; k<=i+1; k++)

x = x+1;

5. Oletetaan, että taulukon alkiot saavat kokonaislukuarvoja väliltä 1, …, 10. Onko mahdollista lajitella taulukko, jossa on n annettua lukua väliltä 1, …, 10, suuruusjärjestykseen ajassa O(n). Perustele väitteesi.

6. Perustele seuraava väite:

Jos T₁(n) = O(f(n)) ja T₂(n) = O(g(n)), niin T₁(n)* T₂(n) = O(f(n)* g(n)).