1.5 Rekurrenser — iterasjon, substitusjon og splitt-og-hersk

Iterasjonsmetoden for **eksakte** svar, substitusjonsmetoden for induksjonsverifikasjon, og splitt-og-hersk-paradigmet (binærsøk) som gir rekurrensene.

55 min

8 oppgaver

Rekurrenseriterasjonsubstitusjonsplitt-og-hersk

Din fremgang i kapitlet

0 / 8 oppgaver

Kapitlets plass i kurset

Bygger på

1.4Rekurrenser — masterteoremet

Brukes videre i

1.6DRILL — Rekurrensløsning med navngitt metode 6.1Dynamisk programmering — mekanikk

Rekurrenser er registrert i 13 av de 17 settene i grunnlaget (76 %), og
splitt-og-hersk-analyse i 12 av 17 (71 %). Grunnlaget er de 17 settene fra
august 2015 til august 2023 som er gjennomgått tema for tema — det er nevneren
hver gang boka oppgir en prosent.

Sjangeren er den samme som i kap. 1.4:

- Sjanger B — rekurrensløsning med navngitt metode, altså at du sier
hvilken metode du bruker og oppgir svaret på den formen oppgaven ber om. Det
siste er avgjørende: iterasjon gir et eksakt uttrykk, masterteoremet gir
en asymptotisk grense. Blander du de to formene, svarer du på feil spørsmål.

Høyeste prioritet — dette må sitte for iterasjon og substitusjon.
Splitt-og-hersk som designidé er ett hakk lavere: bør sitte.

Det du skal kunne skille mellom etter dette kapitlet:

Oppgaven sier	Metode	Svarform
«finn et eksakt uttrykk»	iterasjon	et lukket uttrykk, for eksempel $n(n+1)/2$
«vis at $T(n) = O(\dots)$ »	substitusjon	induksjonssteget ført ferdig
«løs rekurrensen» på $aT(n/b)+f(n)$ -form	masterteoremet	$\Theta(\dots)$ med tilfellet oppgitt
«hvor mange nivåer?»	rekursjonstreet	$\Theta(\log_b n)$

Slik er kapitlet lagt opp (55 min):

Innhold	Tid
Iterasjonsmetoden og de eksakte svarene	ca. 18 min
Substitusjonsmetoden	ca. 15 min
Splitt og hersk, og binærsøk	ca. 16 min
Antall nivåer, og hvilken metode når	ca. 6 min

Forkunnskaper

- kap. 1.4 — masterteoremet. Dette sto der: en rekurrens
på formen $T(n) = aT(n/b) + f(n)$ løses ved å sammenligne $f(n)$ med
$n^{\log_b a}$ , og tilfelle 2 gjelder når $f(n) = \Theta(n^{\log_b a}\lg^k n)$
med $k \ge 0$ . Teoremet gir alltid et asymptotisk svar. Dette kapitlet
handler om de to metodene som tar over der teoremet ikke rekker.
- kap. 1.1 — de asymptotiske symbolene, og at
$\lg n = \log_2 n$ .

Summeformler brukes i hvert eneste iterasjonssvar. Er de ustøe:
Rekker og summasjon for $1 + 2 + \dots + n = n(n+1)/2$ , og
Geometriske følger og rekker for
$1 + 2 + 4 + \dots + 2^{n-1} = 2^n - 1$ .

Induksjon er hele substitusjonsmetoden. Grundig gjennomgang:
Induksjonsbevis. Mykere første møte:
Induksjon.

Er rekursjon som ferdighet fersk, er
Rekursjon — spore og skrive et godt sted å begynne, og
Søking: sekvensielt søk og binærsøk viser binærsøket i
kode før vi analyserer det her.

Notasjons- og pseudokodeliste

Iterasjonsmetoden og de eksakte svarene (~18 min)

Masterteoremet er raskt, men det kan bare to ting: kjenne igjen formen
$aT(n/b) + f(n)$ , og gi et asymptotisk svar. Kommer oppgaven med en rekurrens
der størrelsen krymper ved subtraksjon — $T(n) = T(n-1) + \text{noe}$ —
faller den utenfor. Og ber oppgaven om et eksakt uttrykk, er masterteoremet
ubrukelig uansett form.

Da bruker du iterasjonsmetoden: du setter rekurrensen inn i seg selv
gjentatte ganger, ser mønsteret, og summerer.

Iterasjonsmetoden

i

✏️Eksempel 1: Et eksakt uttrykk ved teleskopering

Løs $T(n) = T(n-1) + n$ med grunntilfellet $T(0) = 0$ . Finn et eksakt
uttrykk for $T(n)$ .

Steg 1 — sett inn i seg selv.

$T(n) = T(n-1) + n$
$T(n) = \big(T(n-2) + (n-1)\big) + n = T(n-2) + (n-1) + n$
$T(n) = T(n-3) + (n-2) + (n-1) + n$

Intuisjon: hver innsetting flytter oss ett hakk nedover og etterlater ett
ledd på gulvet. Leddene som blir liggende igjen, er nettopp tallene $n$ ,
$n-1$ , $n-2$ og så videre.

Steg 2 — det generelle leddet. Etter $i$ innsettinger:

$T(n) = T(n-i) + (n-i+1) + (n-i+2) + \dots + n$

Intuisjon: argumentet er sunket med $i$ , og vi har samlet opp de $i$ største
tallene opp til $n$ .

Steg 3 — treff grunntilfellet. Vi vil ha $T(n-i) = T(0)$ , altså $i = n$ . Da
blir

$T(n) = T(0) + 1 + 2 + \dots + n = 0 + \sum_{j=1}^{n} j$

Intuisjon: iterasjonen stopper når argumentet når bunnen. Er
grunntilfellet $T(0)=0$ , bidrar det ingenting til summen.

Steg 4 — summer.

$T(n) = \frac{n(n+1)}{2}$

Svaret oppgaven ber om: $T(n) = \dfrac{n(n+1)}{2}$ .

Kontroll: $T(1) = 1$ , $T(2) = 3$ , $T(3) = 6$ — og rekurrensen gir
$T(1) = T(0)+1 = 1$ , $T(2) = 1+2 = 3$ , $T(3) = 3+3 = 6$ . Stemmer.

Merk hva som skjer hvis oppgaven i stedet ba om en asymptotisk grense. Da
er svaret $\Theta(n^2)$ , og det er en helt annen svarform. Les spørsmålet.

📝Oppgave 1

(Innstegsoppgave, sjanger B — rekurrensløsning med navngitt metode, altså at du
sier hvilken metode du bruker og oppgir svaret på riktig form.)

Løs $T(n) = T(n-1) + 3$ med $T(0) = 5$ . Finn et eksakt uttrykk.

✏️Eksempel 2: Når arbeidet dobles nedover

Løs $T(n) = T(n-1) + 2^{n-1}$ med $T(0) = 0$ . Finn et eksakt uttrykk.

Steg 1 — sett inn.

$T(n) = T(n-1) + 2^{n-1}$
$T(n) = T(n-2) + 2^{n-2} + 2^{n-1}$
$T(n) = T(n-3) + 2^{n-3} + 2^{n-2} + 2^{n-1}$

Intuisjon: leddene som blir liggende igjen, er potenser av 2 — og de
halveres for hvert hakk nedover.

Steg 2 — det generelle leddet. Etter $i$ innsettinger:

$T(n) = T(n-i) + 2^{n-i} + 2^{n-i+1} + \dots + 2^{n-1}$

Steg 3 — treff grunntilfellet. Med $i = n$ får vi $T(0) = 0$ , og summen
blir alle potensene fra $2^0$ til $2^{n-1}$ .

Steg 4 — summer den geometriske rekken.

$T(n) = \sum_{j=0}^{n-1} 2^{j} = 2^n - 1$

Intuisjon: summen av alle potenser opp til $2^{n-1}$ er nøyaktig én mindre
enn den neste potensen — det er den geometriske rekken med kvotient 2.

Svaret oppgaven ber om: $T(n) = 2^n - 1$ .

Kontroll: $T(1) = 1$ , $T(2) = 3$ , $T(3) = 7$ , $T(4) = 15$ . Rekurrensen gir
$T(1) = 0 + 1 = 1$ , $T(2) = 1 + 2 = 3$ , $T(3) = 3 + 4 = 7$ , $T(4) = 7+8 = 15$ .
Stemmer.

Asymptotisk er dette $\Theta(2^n)$ — men det var ikke det oppgaven spurte om.

📝Oppgave 2

Eksamensnivå, sjanger B

Løs $T(n) = 2T(n-1) + 1$ med $T(0) = 0$ . Finn et eksakt uttrykk, og navngi
metoden.

📝Oppgave 3

Eksamensnivå, sjanger B

En rutine kaller seg selv på et array som er to elementer kortere, og gjør $n$
enheter arbeid i hvert kall: $T(n) = T(n-2) + n$ for like $n$ , med $T(0) = 0$ .

Finn et eksakt uttrykk for like $n$ .

Substitusjonsmetoden (~15 min)

Den andre metoden svarer på et annet spørsmål. Iterasjon finner et svar;
substitusjon verifiserer et svar du allerede har gjettet.

Det høres bakvendt ut, men det er en fullverdig bevismetode — og det er den
oppgaven ber om når den sier «vis at $T(n) = O(n\lg n)$ ».

Substitusjonsmetoden

n

📜Induksjonssteget, ledd for ledd

Påstanden vi vil vise:

T(n) \le c\,n\lg n

for en konstant

c > 0

og
alle

n \ge n_0

, gitt rekurrensen

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

Induksjonshypotesen: anta at påstanden holder for alle argumenter mindre
enn $n$ , spesielt for $n/2$ :

$T(n/2) \le c\,\frac{n}{2}\lg\frac{n}{2}$

Steget:

$T(n) = 2T(n/2) + n \le 2c\,\frac{n}{2}\lg\frac{n}{2} + n = c\,n\lg\frac{n}{2} + n$

Intuisjon: vi har byttet ut det vi ikke kjenner, $T(n/2)$ , med det
hypotesen lover om det. Det er hele trikset.

$= c\,n(\lg n - \lg 2) + n = c\,n\lg n - c\,n + n$

Intuisjon: logaritmeregelen $\lg(n/2) = \lg n - 1$ gjør at det faller ut et
helt ledd $-c\,n$ . Det leddet er reserven vår.

$\le c\,n\lg n \quad\text{når}\quad -c\,n + n \le 0, \text{ altså når } c \ge 1$

Intuisjon: vi er i mål så snart reserven $c\,n$ er minst like stor som det
ekstra arbeidet $n$ på dette nivået.

Grunntilfellet: for $n = 2$ er $T(2) = 2T(1) + 2$ . Med $T(1)$ konstant kan
vi velge $c$ stor nok til at $T(2) \le c\cdot 2\lg 2 = 2c$ . Merk at $n = 1$
ikke duger som grunntilfelle: $c\cdot 1 \cdot \lg 1 = 0$ , og $T(1) > 0$ .

Konklusjon: $T(n) = O(n\lg n)$ .

Numerisk kontroll: for $c = 2$ og $T(1) = 1$ er $T(n) \le 2n\lg n$ for alle
$n$ fra 2 til 4999 — sjekket ved å regne ut begge sider.

📝Oppgave 4

Eksamensnivå, sjanger B

Vis ved substitusjon at $T(n) = T(n-1) + n$ gir $T(n) = O(n^2)$ .

Før induksjonssteget ferdig.

📝Oppgave 5

Eksamensnivå, sjanger…

En kandidat vil vise at $T(n) = 2T(n/2) + n$ gir $T(n) = O(n)$ , og skriver:

«Anta $T(n/2) \le c\,(n/2)$ . Da er $T(n) \le 2c(n/2) + n = cn + n = O(n)$ .»

Er beviset gyldig? Svar ja eller nei, og forklar nøyaktig hvor det svikter.

Splitt og hersk, og binærsøk (~16 min)

Rekurrensene kommer ikke fra ingenting. De kommer fra en bestemt måte å bygge
algoritmer på, og den er verdt å ha et navn på.

Splitt og hersk

T(n) = aT(n/b) + f(n)

📜Pseudokode-kontrakt: `Bisect`

Antagelser om representasjon. Arrayet er A[1..n], indeks fra 1, og det er
sortert stigende. Rutinen er skrevet iterativt med to grenser lo og hi;
den rekursive varianten gjør nøyaktig det samme.

Prebetingelse: A[1..n] er sortert.
Postbetingelse: rutinen returnerer en indeks i med A[i] = v hvis v
finnes i arrayet, og NIL ellers.

Bisect(A, v)
  Input:  sortert array A[1..n] og en verdi v
  Output: en indeks i med A[i] = v, ellers NIL
  lo = 1
  hi = A.length
  while lo <= hi
      mid = floor((lo + hi) / 2)
      if A[mid] == v
          return mid
      else if A[mid] < v
          lo = mid + 1
      else
          hi = mid - 1
  return NIL
  Kjoeretid: Theta(lg n) verste

Invarianten i én setning: hvis v finnes i arrayet, ligger den i
A[lo..hi].

Kjøretid: hver runde halverer intervallet, og arbeidet per runde er
konstant, altså

$T(n) = T(n/2) + \Theta(1) \;\Rightarrow\; T(n) = \Theta(\lg n)$

Her er $a = 1$ og $b = 2$ , så $n^{\log_2 1} = n^0 = 1$ , og $f(n) = \Theta(1) = \Theta(n^0\lg^0 n)$ treffer tilfelle 2 med $k = 0$ . Svaret blir
$\Theta(\lg^1 n) = \Theta(\lg n)$ .

Numerisk kontroll: verste antall runder er nøyaktig
$\lfloor \lg n\rfloor + 1$ — kontrollert for alle $n$ fra 1 til 1999 ved å
regne ut den dypeste stien i søket.

Legg merke til at bare ÉN av de to halvdelene besøkes. Det er derfor
$a = 1$ , og det er derfor binærsøk er logaritmisk mens Merge-Sort, som må
inn i begge halvdelene, er $\Theta(n\lg n)$ .

✏️Eksempel 3: Tre splitt-og-hersk-algoritmer, tre rekurrenser

For hver av de tre: sett opp rekurrensen og løs den. Oppgi metoden.

a) Binærsøk i et sortert array: én halvdel besøkes, konstant arbeid per
nivå.
b) Merge-Sort: begge halvdelene besøkes, lineær fletting.
c) En rutine som deler inputen i fire like deler, løser alle fire
rekursivt, og bruker lineær tid på å sette sammen.

T(n) = T(n/2) + \Theta(1)

Metode: masterteoremet. $a = 1$ , $b = 2$ , $n^{\log_2 1} = 1$ , og
$f(n) = \Theta(1)$ — tilfelle 2 med $k = 0$ .

$T(n) = \Theta(\lg n)$

b) $T(n) = 2T(n/2) + \Theta(n)$ .

Metode: masterteoremet. $a = 2$ , $b = 2$ , $n^{\log_2 2} = n$ , og
$f(n) = \Theta(n)$ — tilfelle 2 med $k = 0$ .

$T(n) = \Theta(n\lg n)$

c) $T(n) = 4T(n/4) + \Theta(n)$ .

Metode: masterteoremet. $a = 4$ , $b = 4$ , $n^{\log_4 4} = n$ , og
$f(n) = \Theta(n)$ — tilfelle 2 med $k = 0$ .

$T(n) = \Theta(n\lg n)$

Det som er verdt å legge merke til: b) og c) gir samme svar. Å dele i fire
i stedet for to endrer bare konstanten, ikke veksten. Det som virkelig
skiller a) fra de to andre, er at a) besøker én del i stedet for alle — og
det ser du på $a$ , ikke på $b$ .

Svarformen på eksamen: rekurrensen, metodenavnet, tilfellet og svaret. Fire
korte linjer per deloppgave.

📝Oppgave 6

Eksamensnivå, sjanger B

En rutine deler inputen i to halvdeler, går rekursivt inn i begge, og
bruker $\Theta(n^2)$ på å kombinere.

a) Sett opp rekurrensen.
b) Løs den med masterteoremet, og oppgi tilfellet.

📝Oppgave 7

Eksamensnivå, sjanger H

Et sortert array A[1..n] inneholder $n$ forskjellige heltall, som kan
være både negative og positive. Du skal avgjøre om det finnes en indeks $i$
med A[i] = i, og i så fall oppgi en slik indeks.

Beskriv en algoritme som bruker $O(\lg n)$ tid.

Antall nivåer, og hvilken metode når (~6 min)

Et fast delspørsmål er «hvor mange nivåer har rekursjonstreet?» — eller, i
noen formuleringer, «hvor mange ganger kalles rutinen på hverandre før den
stopper?»

Antall nivåer i rekursjonstreet

T(n) = aT(n/b) + f(n)

📝Oppgave 8

Eksamensnivå, sjanger B

For hver rekurrens: hvor mange nivåer har rekursjonstreet, og hvilken metode
ville du valgt for å løse den?

a) $T(n) = 3T(n/3) + n$
b) $T(n) = T(n-1) + \lg n$
c) $T(n) = 2T(n/4) + 1$

Typiske feil

Den første koster hele oppgaven.

- Å oppgi en asymptotisk grense der oppgaven ber om et eksakt svar. Ber
oppgaven om «et eksakt uttrykk», er $\Theta(n^2)$ feil svar selv om det er
sant. Riktig er $n(n+1)/2$ . Motsatt: ber den om en asymptotisk grense, skal
du ikke bruke plass på det eksakte uttrykket.
- Å teleskopere med feil grunntilfelle. Iterasjonen stopper når argumentet
treffer grunntilfellet, og grunntilfellets verdi skal med i det eksakte
uttrykket. Med $T(0) = 5$ i stedet for $T(0) = 0$ blir svaret et annet.
- Å gjette riktig i substitusjon uten å føre induksjonssteget. Gjetningen
er ikke beviset. Uttellingen ligger i steget der hypotesen settes inn og
restleddet håndteres.
- Å ende induksjonssteget på feil form. Kommer du fram til $cn + n$ når du
antok $cn$ , har du ikke vist påstanden — konstanten har vokst. Dette er
den vanligste substitusjonsfeilen.
- Å bruke masterteoremet der formen ikke passer. $T(n) = T(n-1) + n$ er
ikke på formen $aT(n/b) + f(n)$ . Å si høyt at teoremet ikke gjelder, gir
uttelling; å tvinge det på, gir et svar som ser riktig ut og er galt. Dette
er felle #5 — feil bruk av masterteoremet.
- Å tro at splitt-og-hersk-delproblemer overlapper. De gjør ikke det. Hvert
delproblem løses nøyaktig én gang, og derfor hjelper det ikke å lagre svar.
Overlappende delproblemer er kjennetegnet på dynamisk programmering.

Og den gjennomgående: å ikke navngi metoden. Sjanger B ber eksplisitt om
metoden, og navnet er ett ord.

Metodevalget samlet

Rekurrensens form	Oppgaven ber om	Metode	Svarform
$aT(n/b) + f(n)$	asymptotisk grense	masterteoremet	$\Theta(\dots)$ + tilfellet
$T(n-c) + f(n)$	asymptotisk eller eksakt	iterasjon	lukket uttrykk, evt. $\Theta(\dots)$
hvilken som helst	«finn et eksakt uttrykk»	iterasjon	lukket uttrykk
hvilken som helst	«vis at $T(n) = O(g)$ »	substitusjon	induksjonssteget ført ferdig
hvilken som helst	«hvor mange nivåer?»	rekursjonstreet	$\Theta(\log_b n)$ eller $\Theta(n)$

De faste summene du trenger:

1 + 2 + \dots + n = \frac{n(n+1)}{2}, \qquad 1 + 2 + 4 + \dots + 2^{n-1} = 2^n - 1

1 + \frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^{n}} < 2

Den siste er grunnen til at

T(n) = T(n/2) + \Theta(n)

blir

\Theta(n)

og
ikke

\Theta(n\lg n)

: arbeidet halveres nedover, og summen konvergerer.

Begrepsbank

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

Iterasjonsmetoden

løser en rekurrens ved gjentatt innsetting i seg selv, til mønsteret er tydelig, og summerer så leddene. Gir et eksakt uttrykk, ikke en asymptotisk grense. Krever at grunntilfellet tas med — det er en del av det eksakte svaret.

Teleskopering

T(n) = T(n-1) + n

Substitusjonsmetoden

gjett svaret, og bevis det ved induksjon. Består av grunntilfelle og induksjonssteg; det er steget som gir uttelling. Induksjonssteget må ende på nøyaktig den formen du antok. Blir det et restledd igjen, er gjetningen for optimistisk.

Induksjonshypotesen

n

Splitt og hersk

T(n) = aT(n/b) + f(n)

`Bisect` (binærsøk)

\Theta(\lg n)

Rekurrensen

T(n) = T(n/2) + \Theta(1)

\Theta(\lg n)

Rekurrensen

T(n) = T(n-1) + n

n(n+1)/2

Rekurrensen

T(n) = 2T(n-1) + 1

T

Den aritmetiske summen

1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}

Den geometriske summen

1 + 2 + 4 + \dots + 2^{n-1} = 2^n - 1

Antall nivåer i rekursjonstreet

\Theta(\log_b n)

Grunntilfellet i en rekurrens

T(1)

Eksakt mot asymptotisk svar

T(n)

Felle #5 — feil bruk av masterteoremet

aT(n/b) + f(n)

Sjanger B — rekurrensløsning med navngitt metode

oppgavetypen der du får en rekurrens og skal løse den. Svarformen er metodens navn pluss svaret på riktig form — asymptotisk eller eksakt — og for masterteoremet også hvilket tilfelle. Metodenavnet er ett ord, og det er en del av det som gir uttelling.

Repetisjonsoppgaver

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 Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.