Algoritmer og datastrukturer

Løsningsforslag til øvingsoppgaver: Algoritmeanalyse

Oppgave 1

1. En enkel for-løkke som går n ganger: O(n)

2. To for-løkker "nestet" inn i hverandre. For hver gang ytre løkke går 1 gang, går indre løkke n ganger, totalt blir dette O(n²)

3. To enkle for-løkker som hver går n ganger: O(n)

4. To for-løkker "nestet" inn i hverandre. For hver gang ytre løkke går 1 gang, går indre løkke n² ganger, totalt blir dette O(n³)

5. To for-løkker "nestet" inn i hverandre. For hver gang ytre løkke går 1 gang, går indre løkke i + 1 ganger, totalt vil da indre løkke gå 1 + 2 + 3 + ... + n - 1 = n (n - 1) / 2 ganger, altså blir dette O(n²).

6. Setter vi N = n², ser vi på samme måte som i forrige oppgave at de to innerste løkkene har en arbeidsmengde på O(N²) = O(n⁴). Siden de to innerste løkkene skal utføres n ganger, blir den totale arbeidsmengden her O(n⁵).

7. Denne oppgaven illustrerer et eksempel med 3 nestede løkker, der arbeidsmengden ikke er så enkel å beregne fordi den innerste løkken ligger i en if-setning som sjelden slår til. Hvis det ikke hadde stått noen if-setning foran den innerste løkken, ville dette vært en O(n⁵) algoritme (omtrent samme resonnement som i punkt 6 ovenfor).

   Her vil j-løkken hver gang gå fra j = 0 til j = i² - 1, og if-testen vil derfor bare slå til nøyaktig i ganger hver gang den ytre løkken gjør et gjennomløp (for f.eks. i = 4 vil j gå fra 0 til 15, og testen slår til for j-verdiene 0, 4, 8 og 12.). Vi får da en total arbeidsmengde som er av størrelsesorden O(n⁴)

Oppgave 2

1. t(n) = C · n ms, C = 0.5 / 100 = 0.005
   Kjøretid: t(500) = 0.5 · 500 / 100 ms = 2.5 ms

2. t(n) = C · n · log(n) ms, C = 0.5 / (100 · log(100))
   Kjøretid: t(500) = 0.5 · (500 · log(500)) / (100 · log(100)) ms = 0.5 · 6.75 ms = 3.375 ms

3. t(n) = C · n² ms, C = 0.5 / 100²
   Kjøretid: t(500) = 0.5 · 500² / 100² ms = 12.5 ms

4. t(n) = C · n³ ms, C = 0.5 / 100³
   Kjøretid: t(500) = 0.5 · 500³ / 100³ ms = 62.5 ms

Oppgave 3

1. t(n) = C · n
   C = 0.5 / 100 = 0.005
   t(n) = 60000 = 0.005 · n
   n = 60000 / 0.005 = 12000000 = 12 millioner

2. t(n) = C · n logn
   C = 0.5 / (100 · log(100))
   t(n) = 60000 = 0.5 · (n logn) / (100 · log(100))
   n logn = 60000 · 100 · log(100) / 0.5
   n log₁₀n = 60000 · 100 · 2 / 0.5 = 24 millioner
   Prøving med innsetting av verdier gir omtrent n = 3650000 = 3.65 millioner

3. t(n) = C · n²
   C = 0.5 / 100² = 0.00005
   t(n) = 60000 = 0.00005 · n²
   n² = 60000 / 0.00005 = 1200000000 = 1.2 millarder
   n = 34641

4. t(n) = C · n³
   C = 0.5 / 100³ = 0.0000005
   t(n) = 60000 = 0.0000005 · n³
   n³ = 60000 / 0.0000005 = 120000000000 = 120 millarder
   n = 4932

Oppgave 4

Oppgave 5