Tietorakenteet, kevät 2003
1. Kurssikoe
Tehtävä 2

O(1): esim. alkion lisääminen linkitetyn listan alkuun (päivitetään
aina vakiomäärä linkkejä riippumatta listassa olevien alkioiden
määrästä).

O(log n): esim. binäärihaku n-alkioisesta järjestetystä taulukosta
(jokaisella (vakioaikaisella) askelella jäljellä olevien alkioiden
määrä puolittuu).

O(n): esim. peräkkäishaku n-alkioisesta linkitetystä listasta
(jokaisella (vakioaikaisella) askelella jäljellä olevien alkioiden
määrä vähenee yhdellä).

O(n^2): esim. vaihtojärjestäminen (jokaista taulukon alkiota verrataan
kaikkiin seuraaviin alkioihin).

O(2^n): esim. luentojen Fibonacci-esimerkki. (perusteluja ei vaadittu).

Arvostelusta.

max 8 pistettä, esimerkin tai perustelun virheestä vähenee yksi piste.