Splitt og hersk

Del tabellen på midten, sorter hver halvdel, og flett de to sorterte halvdelene sammen. Det er hele Merge-Sort, og den bruker $\Theta(n \lg n)$ tid i alle tilfeller, der Insertion-Sort bruker $\Theta(n^2)$ i verste tilfelle. Beskrivelsen er kort fordi den lener seg på seg selv: «sorter hver halvdel» er et rekursivt kall.

Splitt og hersk

Dekomponering reduserer en instans til mindre instanser av samme problem. Insertion-Sort kutter av ett element om gangen. Splitt og hersk deler i stedet instansen i flere uavhengige deler, gjerne to like store, løser hver del rekursivt og kombinerer delsvarene. Merge-Sort har alle fire trinnene:

1. Grunntilfelle

   Er instansen liten nok, løses den direkte. En tabell med ett element er allerede sortert.

2. Del

   Del instansen i to eller flere delinstanser som ikke overlapper. Merge-Sort deler tabellen på midten.

3. Løs rekursivt

   Kall algoritmen på hver delinstans for seg: sorter hver halvdel.

4. Kombiner

   Sett delsvarene sammen til et svar for hele instansen: flett de to sorterte halvdelene.

Delingen og kombinasjonen er kjernen i designet, og som regel ligger arbeidet i bare én av dem. I Merge-Sort er delingen triviell, og alt arbeidet ligger i flettingen. Grunntilfellet og de rekursive kallene ser like ut i hver splitt og hersk-algoritme.

Korrektheten er induksjon over problemstørrelsen, akkurat som for annen dekomponering. Grunntilfellet løses direkte. Induksjonshypotesen sier at algoritmen svarer riktig på alle mindre instanser, ikke bare på instansen som er ett element mindre. Det er sterk induksjon, og den trengs fordi en halvdel har omtrent $n/2$ elementer. Delinstansene er mindre enn $n$, så hypotesen gjelder for dem. Induksjonssteget viser at delingen og kombinasjonen gir riktig svar når delsvarene er riktige: er begge halvdelene sortert, gir flettingen en sortert tabell. Argumentet er det samme for hver størrelse, så du viser det én gang for en vilkårlig instans.

Rekurrenser

Kjøretiden til en rekursiv algoritme er kjøretiden til de rekursive kallene pluss arbeidet utenfor dem. Gjør Merge-Sort $n$ operasjoner selv og kaller seg to ganger på halve instansen, er $T(n) = 2T(n/2) + n$. Det er en rekurrens: en ligning der funksjonen står på begge sider, med mindre argument til høyre. Ligningen bestemmer $T$ fullstendig så snart grunntilfellet er kjent, men den sier ikke direkte hva $T(n)$ er. Å løse rekurrensen er å bli kvitt $T$ på høyresiden.

Grunntilfellet er konstant, $T(n) = \Theta(1)$ for $n$ under en grense $n_0$, og rekursjonen stopper etter endelig mange kall. Læreboka kaller dette en algoritmisk rekurrens, og det antas når ikke annet er sagt. Avrunding sløyfes: skriv $n/2$ for $\lfloor n/2 \rfloor$, som om $n$ var en toerpotens. Det endrer ikke den asymptotiske løsningen.

Ta $T(n) = T(n-1) + 1$ med $T(0) = 0$. Sett rekurrensen inn i seg selv til et mønster viser seg, og velg så antall ekspansjoner slik at argumentet treffer grunntilfellet. Det er iterasjonsmetoden:

1. Ekspander

   Rekurrensen gjelder også for $n - 1$, så $T(n-1) = T(n-2) + 1$. Sett dette inn for $T(n-1)$ i $T(n) = T(n-1) + 1$: $T(n) = T(n-2) + 2$.

2. Finn mønsteret

   Etter $i$ ekspansjoner er $T(n) = T(n-i) + i$.

3. Treff grunntilfellet

   Velg $i$ slik at argumentet blir grunntilfellet. $n - i = 0$ gir $i = n$.

4. Sett inn

   $T(n) = T(0) + n = n$.

Binærsøk

Søk etter $v$ i en sortert tabell. Se på elementet i midten. Er det $v$, er du ferdig. Er $v$ mindre, ligger den i venstre halvdel, ellers i høyre, og du søker rekursivt der. Delingen er kjernen, og kombinasjonen finnes ikke: svaret fra det rekursive kallet returneres uendret.

def bisect(A, p, r, v):
  if p > r:
      return None
  q = (p + r) // 2
  if v == A[q]:
      return q
  elif v < A[q]:
      return bisect(A, p, q - 1, v)
  else:
      return bisect(A, q + 1, r, v)

def bisect_iter(A, p, r, v):
  while p <= r:
      q = (p + r) // 2
      if v == A[q]:
          return q
      elif v < A[q]:
          r = q - 1
      else:
          p = q + 1
  return None

Korrektheten følger ved induksjon over lengden på segmentet. Et tomt segment gir NIL, og ett element svarer direkte. Er segmentet lengre, er begge halvdelene kortere, så hypotesen gjelder for dem, og testen i midten velger den halvdelen $v$ må ligge i. Det rekursive kallet er det siste som skjer i prosedyren, så den kan skrives som en løkke som flytter $p$ eller $r$ i stedet. Bevis og kjøretid er de samme.

Ett kall på halve instansen pluss konstant arbeid gir $T(n) = T(n/2) + 1$. Iterasjon halverer argumentet for hver ekspansjon, så det trengs $\lg n$ ekspansjoner for å nå $T(1) = 1$:

Binærsøk bruker $\Theta(\lg n)$ tid.

Merge-Sort

Merge-Sort deler på midten og sorterer halvdelene rekursivt. Kjernen er flettingen: det minste elementet forrest i de to sorterte halvdelene flyttes til neste ledige plass, om og om igjen. Halvdelene kopieres først til to hjelpetabeller $L$ og $R$, hver med en vaktpost $\infty$ bakerst. Når den ene halvdelen er brukt opp, står $\infty$ forrest i den og taper hver sammenligning, så resten tas fra den andre uten en egen test for tom halvdel. Hver runde i løkka plasserer ett element, så flettingen bruker $\Theta(n)$ tid.

inf = float("inf")

def merge_sort(A, p, r):
  if p >= r:
      return
  q = (p + r) // 2
  merge_sort(A, p, q)
  merge_sort(A, q + 1, r)
  merge(A, p, q, r)

def merge(A, p, q, r):
  L = A[p : q + 1] + [inf]
  R = A[q + 1 : r + 1] + [inf]
  i = j = 0
  for k in range(p, r + 1):
      if L[i] <= R[j]:
          A[k] = L[i]
          i = i + 1
      else:
          A[k] = R[j]
          j = j + 1

Læreboka skriver flettingen uten vaktposter, med en egen test for at en halvdel er tom. Flettingen blir like riktig og bruker fortsatt $\Theta(n)$ tid.

To kall på halve instansen pluss $n$ arbeid til flettingen gir $T(n) = 2T(n/2) + n$. Ekspansjonene i iterasjonsmetoden kan tegnes som et rekursjonstre, med ett nivå per ekspansjon og kostnaden summert nivå for nivå. Treet har $n$ på rota, to noder med $n/2$ under, fire med $n/4$ under der igjen, og hvert nivå summerer til $n$. Treet har $\lg n + 1$ nivåer:

Merge-Sort bruker $\Theta(n \lg n)$ i alle tilfeller. Den deler på midten uansett hvordan inputen ser ut.

Substitusjonsmetoden finner ingenting selv, men verifiserer en løsning med induksjon: anta at løsningen holder for mindre argumenter, og vis at den da holder for $n$.

Er påstanden asymptotisk, som $T(n) = O(n)$, skriver du konstanten ut. For $T(n) = T(n-1) + 1$ med $T(0) = 0$ antar du $T(k) \le ck$ for alle $k < n$. Da er

for $c \ge 1$, og grunntilfellet $T(0) = 0 \le c \cdot 0$ stemmer. Den samme $c$ står i hypotesen og i konklusjonen, så $T(n) = O(n)$.

Lurvik-Sort(A, n)
1 Insertion-Sort(A, n)
2 Merge-Sort(A, 1, n)

Smartnes-Sort(A, n)
1 Merge-Sort(A, 1, n)
2 Insertion-Sort(A, n)

Quicksort

Quicksort legger arbeidet i delingen, og kombinasjonen er ingenting. Partition velger det siste elementet $x$ som pivot og ordner resten slik at alt som er mindre enn eller lik $x$ ligger til venstre og alt større til høyre. Så settes $x$ mellom de to delene. Der står den på sin endelige plass og flyttes aldri igjen, og Quicksort sorterer de to delene rekursivt.

Løkka i Partition deler segmentet i soner. Elementene fra $p$ til og med $i$ er små, fra $i + 1$ til og med $j - 1$ store, og fra $j$ og utover ikke sett ennå. Et lite element $A[j]$ bytter plass med det første store, $A[i+1]$, og grensen $i$ rykker ett hakk. Et stort element blir stående. Hver runde ser på ett nytt element, så Partition bruker $\Theta(n)$ tid.

def partition(A, p, r):
  x = A[r]
  i = p - 1
  for j in range(p, r):
      if A[j] <= x:
          i = i + 1
          A[i], A[j] = A[j], A[i]
  A[i + 1], A[r] = A[r], A[i + 1]
  return i + 1

def quicksort(A, p, r):
  if p < r:
      q = partition(A, p, r)
      quicksort(A, p, q - 1)
      quicksort(A, q + 1, r)

Deler pivoten jevnt, er rekurrensen $T(n) = 2T(n/2) + n$, den samme som for Merge-Sort, og kjøretiden $\Theta(n \lg n)$. Havner pivoten helt ytterst hver gang, slik den gjør når tabellen allerede er sortert, får det ene kallet $n - 1$ elementer og det andre ingen. Da er $T(n) = T(n-1) + n$, og iterasjon gir summen $n + (n-1) + \cdots + 1 = n(n+1)/2$, altså $\Theta(n^2)$.

Sortert input er vanlig input, så det verste tilfellet er ikke bare teori. Randomized-Partition bytter et tilfeldig valgt element inn på plass $r$ før delingen. Da er hvert element i segmentet like sannsynlig som pivot, uansett hvordan inputen er ordnet.

Den forventede kjøretiden finner du ved å telle per element. Partition på et segment med $m$ elementer koster $\Theta(m)$, altså en konstant for hvert element i segmentet. Den totale kjøretiden er derfor summen, over alle elementene, av hvor mange delinger hvert element er med i. Følg ett element $e$, og kall en pivot god når rangen i segmentet ligger mellom $m/4$ og $3m/4$. Da får begge delene høyst $3m/4$ elementer, så etter en god pivot har segmentet til $e$ krympet til høyst $3/4$ av størrelsen. Etter $\log_{4/3} n$ gode pivoter har segmentet høyst ett element, så $e$ er med i høyst $\log_{4/3} n$ delinger med god pivot. Halvparten av elementene er gode pivoter, så en tilfeldig pivot er god med sannsynlighet minst $1/2$, og i forventning går det høyst to delinger per god pivot. Element $e$ er dermed med i høyst $2\log_{4/3} n = O(\lg n)$ delinger i forventning, og de $n$ elementene gir til sammen forventet $O(n \lg n)$.

Jevn deling er det beste som kan skje, og den koster allerede $\Theta(n \lg n)$, så forventet kjøretid er $\Theta(n \lg n)$ for enhver input. Regningen bruker bare de tilfeldige valgene og ikke rekkefølgen i inputen. Verste tilfelle er fortsatt $\Theta(n^2)$, men det krever uflaks med de tilfeldige valgene, og ingen input er mer utsatt enn andre.

Den samme tellingen gir gjennomsnittstilfellet for Quicksort med fast pivot. Er alle rekkefølger av inputen like sannsynlige, er det siste elementet i hvert segment like sannsynlig hvilken som helst rang, og snittet over instansene er også $\Theta(n \lg n)$.

Masterteoremet

Mange splitt og hersk-algoritmer gjør $a$ rekursive kall på instanser av størrelse $n/b$ og bruker $f(n)$ på deling og kombinasjon: $T(n) = aT(n/b) + f(n)$. Rekursjonstreet har $\log_b n$ nivåer under rota, nivå $i$ har $a^i$ noder av størrelse $n/b^i$, og nederst står $a^{\log_b n}$ løvnoder. Antallet løvnoder skrives om med $a^{\log_b n} = n^{\log_b a}$. Summert nivå for nivå:

Læreboka kaller $f(n)$ den drivende funksjonen og $n^{\log_b a}$ vannskillefunksjonen. Ta først $f(n) = n^d$. Nivå $i$ koster til sammen $a^i (n/b^i)^d = n^d (a/b^d)^i$, så summen er geometrisk med forholdet $a/b^d$. Er $a/b^d > 1$, altså $d < \log_b a$, vokser leddene nedover, og løvnodene dominerer: $T(n) = \Theta(n^{\log_b a})$. Er $a/b^d = 1$, koster alle de $\log_b n + 1$ nivåene $n^d$, og $T(n) = \Theta(n^d \lg n)$. Er $a/b^d < 1$, krymper leddene, og rota dominerer: $T(n) = \Theta(n^d)$.

Masterteoremet gjelder også andre $f(n)$, så lenge avstanden til vannskillefunksjonen er en faktor $n^\epsilon$ eller $\lg^k n$:

Tilfelle 1, 2 og 3 er de tre utfallene av forholdet $a/b^d$ for $f(n) = n^d$: løvnodene dominerer, alle nivåene koster like mye, eller rota dominerer.

I tilfelle 2 kan $f(n)$ ha en ekstra faktor $\lg^k n$. Nivå $i$ koster da omtrent $n^{\log_b a} \lg^k(n/b^i)$, og summen over nivåene får én faktor $\lg n$ til.

I tilfelle 1 og 3 må avstanden til vannskillefunksjonen være polynomisk, en faktor $n^\epsilon$. En logaritmisk faktor over vannskillefunksjonen havner i tilfelle 2. En logaritmisk faktor under den havner i ingen av tilfellene: i $T(n) = 2T(n/2) + n/\lg n$ er $f(n)$ mindre enn $n$, men ikke polynomisk mindre, og summen nivå for nivå gir $\Theta(n \lg\lg n)$. Teoremet krever også at instansen deles på en konstant faktor $b > 1$, så $T(n) = T(n-1) + n$ har ikke formen.

Betingelsen $a f(n/b) \le c f(n)$ i tilfelle 3 kalles regularitet. Den holder alltid for $f(n) = n^d$ med $d > \log_b a$, for da er $a f(n/b) = (a/b^d) f(n)$ med $a/b^d < 1$.

Sjekk deg selv