1.3 DRILL — Kode → O-notasjon

Systematisk drill i sjanger B: les O-kjøretiden ut av pseudokode med nøstede løkker, halvering og sekvens — de garanterte Del 1-poengene.

80 min

15 oppgaver

DRILLKode → O-notasjon

Din fremgang i kapitlet

0 / 15 oppgaver

Kapitlets plass i kurset

Bygger på

1.2Kjøretidsanalyse fra kode — løkketelling

Dette kapitlet er ren drill på sjanger B — kjøretid fra kode, altså at du
får en pseudokodesnutt og skal svare med ett $O$ -uttrykk. Sjangeren har kommet i
alle sju settene (100 %), ofte med én til to oppgaver per sett, og den ligger
på Del 1, som rettes automatisk.

Det gjør den til den mest forutsigbare poengkilden på hele eksamen: du trenger
ikke kjenne igjen noen algoritme, du trenger ikke huske noen kjøretid, du
trenger bare å telle riktig. Prioritet: høyeste.

To ting fra sensorveiledningene, gjentatt: riktig orden gir poeng selv om
koden har en syntaksfeil, og svaret skal være det strammeste uttrykket —
ett ledd, ingen konstanter.

Slik bruker du kapitlet. Femten oppgaver, ca. fem minutter hver. Du får mest
igjen for å skrive svaret ned på et ark før du åpner fasiten, og for å ta
kontrollen «hva skjer når $n$ dobles?» hver eneste gang. Kapitlet tar rundt 80
minutter, og det er helt greit å dele det over to kvelder — det står et
pausepunkt underveis.

Forkunnskaper

- kap. 1.1 — hva $O$ betyr, vekstordningen og regelen om
det dominerende leddet.
- kap. 1.2 — de fire løkketellingsreglene. Denne drillen
bruker dem og forklarer dem ikke på nytt.

Sitter selve løkkelesingen løst, kan du varme opp med
Løkker: for, while og range eller
DRILL — Kodesporing: «hva skrives ut?», som trener det
mekaniske blikket på kode.

Notasjons- og pseudokodeliste

📜Løsningsoppskriften for sjanger B

Fem steg. Følg dem i rekkefølge, hver gang, også når svaret virker åpenbart.

Steg 1 — marker hver løkke, og skriv rekkevidden i margen. For hver løkke,
still nøyaktig ett spørsmål: hvor mange runder går den? Tre svar er mulige:

- grensen inneholder $n$ (også n/2, n-1, 2n) gir $n$ runder;
- grensen er et fast tall (10, 100, 1000) gir konstant, stryk den;
- tellevariabelen ganges eller deles gir ca. $\log n$ runder.

Steg 2 — gang sammen innenfra og ut. Start med den innerste løkka, gang med
nivået over, og fortsett utover. Skriv ett produkt per blokk.

Steg 3 — legg sammen for sekvens. Blokker som står etter hverandre (samme
innrykk, ikke inni hverandre) legges sammen.

Steg 4 — behold det dominerende leddet og stryk konstantene. Bruk
vekstordningen $1 < \log n < n < n\log n < n^2 < n^3 < 2^n < n!$ . Svaret skal
være ett uttrykk.

Steg 5 — kontrollér med doblingstesten, og si hva $n$ er. Spør: hva skjer
med antall kjøringer når $n$ dobles? Uendret betyr $O(1)$ , ett steg til betyr
$O(\log n)$ , dobling betyr $O(n)$ , firedobling betyr $O(n^2)$ , åttedobling
betyr $O(n^3)$ . Skriv til slutt én setning om hva $n$ teller — det trekkes
eksplisitt for et udefinert $n$ .

Fellekatalogen disse fem stegene fanger: konstant indre løkke lest som
$O(n)$ (steg 1); oversett dobling eller halvering (steg 1); sekvensielle løkker
ganget i stedet for lagt sammen (steg 3); usimplifisert svar (steg 4).

✏️Gjennomarbeidet eksamenscase med sensorkommentarer

Oppgi kjøretiden til denne prosedyren. Snutten er skrevet i eksamensformat: et
Procedure-hode, en kort beskrivelse, og resten er din jobb.

Procedure Sammenstill(A)
  Input:  array A med n tall, indeksert fra 0
  Output: en telling
  n = A.length
  c = 0

  for i = 0 to n-1:
      for j = 0 to 99:
          c = c + 1

  for i = 0 to n-1:
      p = 1
      while p < n:
          c = c + 1
          p = p * 2

  for i = 0 to n-1:
      for j = i to n-1:
          c = c + 1

  return c

Steg 1 — marker løkkene.

Blokk 1: ytre for i går til n-1, altså $n$ runder. Indre for j går til 99
— fast tall, konstant. Sensorkommentar: her sitter det første poenget. En
kandidat som skriver $O(n^2)$ for denne blokken, har lest grensen 99 som om det
sto $n$ .

Blokk 2: ytre for i gir $n$ runder. Indre while p < n med p = p * 2 er en
doblingsløkke, ca. $\log_2 n$ runder. Sensorkommentar: oppdateringslinja står
nederst, og det er der de fleste tellefeilene oppstår. Les den før du
konkluderer.

Blokk 3: trekantløkke — den indre starter på i og går til n-1, altså
$n - i$ runder.

Steg 2 — gang innenfra og ut.

- Blokk 1: $n \cdot 100 = 100n$ .
- Blokk 2: $n \cdot \log_2 n$ .
- Blokk 3: $\displaystyle n + (n-1) + \cdots + 1 = \frac{n(n+1)}{2}$ .

Steg 3 — sekvens. De tre blokkene står etter hverandre:

$100n + n\log n + \frac{n(n+1)}{2}$

Steg 4 — dominerende ledd. Vekstordningen gir
$n < n \log n < n^2$ , så trekantsummen dominerer.

Svar: $O(n^2)$ , der $n$ er antall elementer i A.

Steg 5 — doblingstesten. For $n = 8$ kjører de tre blokkene henholdsvis 800,
24 og 36 ganger. For $n = 16$ : 1600, 64 og 136. Totalt går vi fra 860 til 1800
— litt over dobling foreløpig, men blokk 3 firedobler seg og tar over. For
$n = 128$ er tallene 12 800, 896 og 8256, og fra da av er det trekanten som
styrer. Det stemmer med $O(n^2)$ .

Sensors poengfordeling, slik mønsteret pleier å se ut på en slik oppgave:
hovedmomentet er riktig orden — det er der de fleste poengene ligger. Deretter
gis det uttelling for at du sier hvorfor den konstante løkka ikke teller, og for
at $n$ er definert. Å skrive svaret som $\displaystyle O(100n + n\log n + \frac{n^2+n}{2})$
regnes som riktig telling og feil form: det koster som regel ett poeng.

Modellsvaret, slik du bør skrive det på fire linjer:

«Første blokk: ytre løkke $n$ runder, indre løkke fast antall (100) — bidrar
$O(n)$ . Andre blokk: ytre $n$ runder, indre dobler p og gir ca. $\log n$
runder — bidrar $O(n \log n)$ . Tredje blokk: trekantløkke, $\displaystyle \frac{n(n+1)}{2}$
runder — bidrar $O(n^2)$ . Blokkene står etter hverandre, så det dominerende
leddet gjelder: $O(n^2)$ , der $n$ er antall elementer i arrayet.»

Oppgavene (ca. 5 min hver)

Skriv svaret ned før du åpner fasiten. Sett gjerne opp de fem stegene i margen
de første gangene — etter fem oppgaver går det av seg selv.

📝Oppgave 1

Sjanger B

Oppgi kjøretiden.

Procedure AnnenHver(A)
  Input:  array A med n tall, indeksert fra 0
  Output: summen av annethvert tall
  n = A.length
  s = 0
  i = 0
  while i < n:
      s = s + A[i]
      i = i + 2
  return s

📝Oppgave 2

Sjanger B

Oppgi kjøretiden.

Procedure Rammer(A)
  Input:  array A med n tall, indeksert fra 0
  Output: en telling
  n = A.length
  c = 0
  for i = 0 to n-1:
      for j = 0 to 999:
          c = c + 1
  return c

📝Oppgave 3

Sjanger B

Oppgi kjøretiden.

Procedure Ramse(n)
  Input:  et heltall n
  Output: en telling
  c = 0
  i = 0
  while i < n * n:
      c = c + 1
      i = i + 1
  return c

📝Oppgave 4

Sjanger B

Oppgi kjøretiden.

Procedure Halvveis(A)
  Input:  array A med n tall, indeksert fra 0
  Output: en telling
  n = A.length
  c = 0
  for i = 0 to n-1:
      j = 0
      while j < n / 2:
          c = c + 1
          j = j + 1
  return c

📝Oppgave 5

Sjanger B

Oppgi kjøretiden.

Procedure Nedtelling(n)
  Input:  et heltall n
  Output: en telling
  c = 0
  i = n
  while i > 1:
      for j = 0 to 4:
          c = c + 1
      i = i / 2
  return c

Alle fem handlet om steg 1 i oppskriften: å lese rekkevidden riktig.

- Oppgave 1: additivt steg større enn 1 endrer ikke ordenen.
- Oppgave 2: en stor konstant er fortsatt en konstant.
- Oppgave 3: grensen kan inneholde $n^2$ selv om det bare er én løkke.
- Oppgave 4: n / 2 er ikke et fast tall.
- Oppgave 5: en halverende ytre løkke gir $\log n$ , ikke $n$ .

Bommet du på én av dem, er det verdt å gå tilbake til
kap. 1.2 før du fortsetter — resten av drillen bygger på
at rekkevidden sitter.

— naturlig pausepunkt (du har brukt ca. 35 minutter) —

Resten av oppgavene kombinerer flere nivåer. Framgangsmåten er den samme; det
eneste nye er at du må holde tunga rett i munnen når du ganger sammen.

📝Oppgave 6

Sjanger B

Oppgi kjøretiden.

Procedure Trekant(A)
  Input:  array A med n tall, indeksert fra 0
  Output: en telling
  n = A.length
  c = 0
  for i = 0 to n-1:
      for j = 0 to i-1:
          c = c + 1
  return c

📝Oppgave 7

Sjanger B

Oppgi kjøretiden.

Procedure TreNivaa(A)
  Input:  array A med n tall, indeksert fra 0
  Output: en telling
  n = A.length
  c = 0
  for i = 0 to n-1:
      for j = 0 to n-1:
          for k = 0 to 7:
              c = c + 1
  return c

📝Oppgave 8

Sjanger B

Oppgi kjøretiden, og svar også på om det gjør noen forskjell at
tellevariabelen ganges med 3 og ikke med 2.

Procedure Tredeling(A)
  Input:  array A med n tall, indeksert fra 0
  Output: en telling
  n = A.length
  c = 0
  for i = 0 to n-1:
      j = 1
      while j < n:
          c = c + 1
          j = j * 3
  return c

📝Oppgave 9

Sjanger B

Oppgi kjøretiden. Her kalles en annen prosedyre inni løkka.

Procedure SjekkAlle(A)
  Input:  array A med n tall, indeksert fra 0, sortert stigende
  Output: antall tall i A som også finnes i A (trivielt n, men tell arbeidet)
  n = A.length
  c = 0
  for i = 0 to n-1:
      if BinærSøk(A, A[i]):
          c = c + 1
  return c

Anta at BinærSøk(A, x) er den vanlige varianten som halverer søkeområdet og
svarer true eller false, med kjøretid $O(\log n)$ på et sortert array med
$n$ elementer.

📝Oppgave 10

Sjanger B

Oppgi kjøretiden.

Procedure ToBlokker(A)
  Input:  array A med n tall, indeksert fra 0
  Output: en telling
  n = A.length
  c = 0

  p = 1
  while p < n:
      c = c + 1
      p = p * 2

  for i = 0 to n-1:
      for j = 0 to n-1:
          c = c + 1

  return c

De fem siste (ca. 25 min)

Disse er på det nivået de tyngste sjanger B-oppgavene har ligget. Ta dem gjerne
med klokke: fem minutter hver, og skriv begrunnelsen i tre setninger slik
modellsvaret i sensor-casen viste.

📝Oppgave 11

Sjanger B, eksamensnivå

Oppgi kjøretiden.

Procedure Femdobbel(n)
  Input:  et heltall n
  Output: en telling
  c = 0
  for a = 0 to n-1:
      for b = 0 to n-1:
          for d = 0 to n-1:
              for e = 0 to n-1:
                  for f = 0 to n-1:
                      c = c + 1
  return c

📝Oppgave 12

Sjanger B, eksamensnivå

Oppgi kjøretiden.

Procedure Trippeltrekant(A)
  Input:  array A med n tall, indeksert fra 0
  Output: en telling
  n = A.length
  c = 0
  for i = 0 to n-1:
      for j = 0 to i-1:
          for k = 0 to j-1:
              c = c + 1
  return c

📝Oppgave 13

Sjanger B, eksamensnivå

Oppgi kjøretiden.

Procedure Lagvis(A)
  Input:  array A med n tall, indeksert fra 0
  Output: en telling
  n = A.length
  c = 0
  p = 1
  while p < n:
      for i = 0 to n-1:
          for j = i to n-1:
              c = c + 1
      p = p * 2
  return c

📝Oppgave 14

Sjanger B, eksamensnivå

Oppgi kjøretiden, og si hvilken av de to blokkene som
avgjør svaret.

Procedure Todelt(A)
  Input:  array A med n tall, indeksert fra 0
  Output: en telling
  n = A.length
  c = 0

  for i = 0 to n-1:
      m = n
      while m > 1:
          c = c + 1
          m = m / 2

  for i = 0 to n-1:
      for j = 0 to n-1:
          c = c + 1

  return c

📝Oppgave 15

Sjanger B,…

Oppgi kjøretiden for hver av de to prosedyrene,
og forklar forskjellen med én setning.

Procedure Ned(n)
  Input:  et heltall n
  Output: ingenting; gjør et fast arbeid per kall
  if n <= 1:
      return
  gjør et fast stykke arbeid
  Ned(n / 2)

Procedure Steg(n)
  Input:  et heltall n
  Output: ingenting; gjør et fast arbeid per kall
  if n <= 0:
      return
  gjør et fast stykke arbeid
  Steg(n - 1)

Typiske feil — fellekatalogen for sjanger B

Samlet, slik at du kan lese den rett før eksamen.

- Konstant indre løkke lest som $O(n)$ . for j = 0 to 999 er 1000 runder,
ikke $n$ . Test: står det n i grensen?
- Oversett dobling eller halvering. j = j * 2 og m = m / 2 gir
$\log n$ runder. Oppdateringslinja står ofte nederst i løkka.
- Sekvensielle blokker ganget i stedet for lagt sammen. Se på innrykket:
inni betyr gang, etter betyr legg sammen.
- Antall løkker forvekslet med antall runder. Én løkke til n * n er
$O(n^2)$ ; tre nøstede løkker der to er konstante, er $O(n)$ .
- En linje som kaller en prosedyre behandlet som $O(1)$ . Kallet arver
kjøretiden til det det kaller.
- Usimplifisert svar. $O(8n^2 + n)$ er riktig regnet og feil levert. Ett
ledd, ingen konstanter.
- n uten definisjon. Dette er felle #10 i bokas register — å oppgi
kjøretid eller drøfte uten å si hva problemstørrelsen teller. Én setning
holder.
- Å hoppe over oppgaven fordi koden ser rar ut. Riktig orden gir poeng selv
om snutten ikke ville kompilert. Svar alltid.

Begrepsbank

Begrepsbanken under er flashcard- og repetisjonsstoff — den gjentar det du
nettopp har lest. Hopp trygt over den ved førstegangslesing; tidsanslaget for
kapitlet gjelder oppgavene.

Sjanger B — kjøretid fra kode

O

Femstegsoppskriften

n

Doblingstesten

n

Rekkevidde med n i seg

O

Multiplikativ oppdatering

\log n

Additiv oppdatering

n

Trekantsum

\displaystyle 1 + 2 + \cdots + n = \frac{n(n+1)}{2}

Kall arver kjøretid

O(1)

Ett uttrykk, ingen konstanter

O

Løkketelling framfor rekurrensligninger

IN2010 analyserer kjøretid — også for rekursive prosedyrer — ved å telle arbeid og nivåer. Rekurrensligninger, substitusjonsmetoden og de generelle teoremene for å løse slike ligninger er ikke pensum . For rekursjon er spørsmålet alltid det samme: hvor mange kall gjør hvert kall, hvor mange nivåer blir det, og hva koster hvert kall?

Repetisjon — kortet du tar med til eksamen

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.