1.4 Rekurrenser — masterteoremet

En ligning som uttrykker kjøretiden for et problem av størrelse $n$ ved hjelp av
kjøretiden for mindre inputstørrelser. Den beskriver arbeidet, men oppgir det
ikke — svaret må regnes fram.

Standardformen i dette faget er $T(n) = aT(n/b) + f(n)$: algoritmen lager $a$
delproblemer av størrelse $n/b$ og bruker $f(n)$ på alt annet.

Kravet for at masterteoremet skal kunne brukes, er at rekurrensen faktisk er på
denne formen — med $a \ge 1$ og $b > 1$. Rekurrenser som $T(n) = T(n-1) + n$
krymper ved subtraksjon i stedet for divisjon og faller utenfor.

Den minste inputen algoritmen ikke deler opp videre, og den verdien rekursjonen
stopper på. Uten et grunntilfelle er en rekurrens uendelig.

For algoritmiske rekurrenser antas $T(k) = \Theta(1)$ for en konstant $k$ — å
sortere ett element eller søke i et array med ett element tar konstant tid.

Kravet er mildere enn man skulle tro: et oppgitt grunntilfelle som $T(0) = 0$
eller $T(1) = 1$ er som regel uten betydning for det asymptotiske svaret, og
masterteoremet spør aldri etter det. Skal du derimot oppgi et eksakt
uttrykk, betyr grunntilfellet alt.

Antall løvnoder i rekursjonstreet, altså hvor mye arbeid som ligger helt i
bunnen av rekursjonen. Det er den ene av de to størrelsene masterteoremet
sammenligner.

Regnes ut ved å ta logaritmen til $a$ med grunntall $b$. For $T(n)=2T(n/2)+n$ er
$\log_2 2 = 1$, altså $n^1 = n$. For $T(n)=9T(n/3)+n$ er $\log_3 9 = 2$, altså
$n^2$.

Kravet er å regne dette først, hver eneste gang. Alle tre tilfellene er
formulert som en sammenligning mot nettopp dette uttrykket, så uten det kan du
ikke velge tilfelle.

Det tilfellet der rekursjonen dominerer: arbeidet utenom er så lite at det er
løvnodene som bestemmer kjøretiden.

Betingelsen er $f(n) = O(n^{\log_b a - \varepsilon})$ for en konstant
$\varepsilon > 0$, og svaret er $T(n) = \Theta(n^{\log_b a})$.

Kravet som lett overses, er at $\varepsilon$ må være strengt positiv: gapet
må være en hel potens av $n$. At $f(n)$ bare er litt mindre enn $n^{\log_b a}$,
for eksempel med en logaritmefaktor, er ikke nok.

Det tilfellet der arbeidet på toppen og arbeidet i bunnen er like store, slik at
hvert nivå i rekursjonstreet koster omtrent det samme.

Betingelsen er $f(n) = \Theta(n^{\log_b a}\lg^{k} n)$ med $k \ge 0$, og svaret er
$T(n) = \Theta(n^{\log_b a}\lg^{k+1} n)$.

Kravet er at $k$ er ikke-negativ. Den ekstra logaritmen i svaret kommer fra
antall nivåer i treet: like mye arbeid på hvert av $\log_b n$ nivåer gir én
logaritme ekstra.

Antall logaritmefaktorer i $f(n)$ utover $n^{\log_b a}$. Den avgjør hvor mange
logaritmer som står i svaret, og den skal alltid leses av før du konkluderer.

Er $f(n) = n^{\log_b a}$ glatt, er $k = 0$ og svaret får én logaritme. Er
$f(n) = n^{\log_b a}\lg n$, er $k = 1$ og svaret får to. Regelen er alltid
$k \to k+1$.

Kravet er at $k$ må være ikke-negativ. Er $f(n)$ mindre enn $n^{\log_b a}$ med
en logaritmefaktor — altså $k = -1$ — faller rekurrensen utenfor den varianten av
teoremet som brukes i dette faget.

Det tilfellet der arbeidet på toppen dominerer: oppdelingen og sammensettingen
koster så mye at rekursjonen blir uvesentlig.

Betingelsen er $f(n) = \Omega(n^{\log_b a + \varepsilon})$ for en konstant
$\varepsilon > 0$, og svaret er $T(n) = \Theta(f(n))$.

Kravet som skiller dette tilfellet fra de to andre, er at det har to
betingelser: gapet må være en hel potens av $n$, og i tillegg må
regularitetsbetingelsen holde.

Tilleggskravet i tilfelle 3: arbeidet på ett nivå skal være en fast brøkdel
mindre enn arbeidet på nivået over, slik at summen nedover faktisk krymper.

Formelt: $af(n/b) \le c\,f(n)$ for en konstant $c < 1$ og alle store nok $n$.

Kravet er nesten alltid oppfylt for de $f(n)$-ene som dukker opp på eksamen —
polynomer og polynomer ganger logaritmer. For $T(n)=2T(n/2)+n^2$ er
$2(n/2)^2 = n^2/2$, altså $c = 1/2$, og betingelsen holder. Skriv én linje om
den når du bruker tilfelle 3; det er den linja løsningsforslagene ser etter.

Hvor dypt rekursjonen går før den treffer grunntilfellet. Det er antall ganger
du kan dele $n$ på $b$ før du er nede på en konstant.

Svaret er $\Theta(\log_b n)$, og siden logaritmer med ulikt grunntall skiller seg
med en konstant faktor, er det samme klasse som $\Theta(\lg n)$.

Kravet er å ikke blande dybde og bredde: $a$ påvirker antall løvnoder
($n^{\log_b a}$), ikke antall nivåer. For $b = 2$ og $n = 1024$ er det 10 nivåer
under rota, altså 11 nivåer i alt.

De rekurrensene som faller utenfor bruksområdet, og som derfor krever en annen
metode.

Fire typer: størrelsen krymper ved subtraksjon ($T(n)=T(n-1)+n$), delene er
ulikt store ($T(n)=T(n/3)+T(2n/3)+n$), $f(n)$ ligger i gapet mellom tilfellene
($T(n)=2T(n/2)+n/\lg n$), eller $a < 1$ eller $b \le 1$.

Kravet er å si det høyt i besvarelsen. Å tvinge teoremet på en slik rekurrens
gir et svar som ser riktig ut og er galt — og å påpeke at det ikke gjelder, gir
uttelling.

Den formen en rekurrens må ha for at teoremet skal kunne brukes: $a$ like store
delproblemer av størrelse $n/b$, pluss $f(n)$ arbeid utenom rekursjonen.

Skrevet ut: $T(n) = aT(n/b) + f(n)$ med $a \ge 1$ og $b > 1$.

Kravene på $a$ og $b$ er ufravikelige. Er $b = 1$, krymper problemet aldri; er
$a < 1$, gir rekursjonen ingen mening. Og delene må være like store — én felles
$b$ for alle delproblemene.

Størrelsen på gapet mellom $f(n)$ og $n^{\log_b a}$, målt i potenser av $n$.
Den finnes bare i tilfelle 1 og 3, og den må være strengt positiv.

I tilfelle 1 skal $f(n) = O(n^{\log_b a - \varepsilon})$; i tilfelle 3 skal
$f(n) = \Omega(n^{\log_b a + \varepsilon})$.

Kravet betyr i praksis at gapet må være en hel potens av $n$. Er avstanden bare
en logaritme, finnes ingen slik $\varepsilon$, og du er i tilfelle 2 i stedet.
Det er nettopp derfor tilfelle 2 må finnes.

Det første steget i enhver masterteorem-oppgave: finn det tallet du må opphøye
$b$ i for å få $a$.

Eksempler: $\log_2 4 = 2$ fordi $2^2 = 4$; $\log_3 9 = 2$ fordi $3^2 = 9$;
$\log_4 8 = 3/2$ fordi $4^{1{,}5} = 8$; $\log_5 5 = 1$; $\log_2 1 = 0$.

Kravet er å ha grunntallet riktig vei: $b$ er grunntallet og $a$ er argumentet.
$\log_2 8 = 3$, mens $\log_8 2 = 1/3$ — en ombytting her gir feil tilfelle og
feil svar. Verdien behøver ikke være et helt tall.

Den vanligste feilen i rekurrensoppgaver: å velge tilfelle på øyemål i stedet
for å regne.

Tre former: glemt logaritmefaktor når $f(n) = \Theta(n^{\log_b a})$, bruk av
tilfelle 2 med negativ $k$, og feil utregnet $\log_b a$.

Kravet som fjerner alle tre, er å skrive $n^{\log_b a}$ eksplisitt, deretter
$f(n)$ på formen $n^{\log_b a}\lg^k n$, og først da velge tilfelle. To ekstra
linjer på kladden, og fellen er borte.

Oppgavetypen dette kapitlet trener: du får en rekurrens og skal oppgi hva den
løser til.

Den er med i 76 % (13 av de 17 settene i grunnlaget). Svarformen er 1–3 linjer:
metodens navn, svaret på riktig form, og hvilket masterteorem-tilfelle du
brukte.

Kravet som skiller full fra delvis uttelling, er at metoden navngis. Å skrive
bare $\Theta(n\lg n)$ uten å si «masterteoremet, tilfelle 2» besvarer ikke hele
spørsmålet.

Rekurrensen for Merge-Sort og for enhver algoritme som deler problemet i to
like halvdeler og bruker lineær tid på å sette dem sammen igjen.

Her er $\log_2 2 = 1$, så $n^{\log_b a} = n$, som er nøyaktig $f(n)$. Tilfelle 2
med $k = 0$ gir $\Theta(n\lg n)$.

Kravet du bør merke deg, er at $k = 0$ er lovlig. Med et krav om strengt
positiv $k$ ville denne aller mest sentrale rekurrensen falt utenfor teoremet.

Rekurrensen for Binary-Search og for enhver algoritme som halverer
søkeområdet og gjør konstant arbeid per steg.

Her er $a = 1$ og $\log_2 1 = 0$, så $n^{\log_b a} = n^0 = 1$, som er nøyaktig
$f(n)$. Tilfelle 2 med $k = 0$ gir $\Theta(\lg n)$.

Kravet som overrasker, er at $a = 1$ er tillatt — teoremet krever $a \ge 1$, ikke
$a > 1$. Én rekursiv gren er nok.

To ulike størrelser som ofte forveksles. Dybden er hvor mange nivåer treet har;
bredden er hvor mange løvnoder det ender med.

Dybden er $\Theta(\log_b n)$ og styres av $b$ alene. Bredden er $n^{\log_b a}$ og
styres av både $a$ og $b$.

Kravet er å lese spørsmålet nøye: «hvor mange nivåer?» og «hvor mye arbeid gjøres
i bunnen?» har ulike svar, og delspørsmålet om nivåer går igjen i grunnlaget.