Splitt og hersk

Når en instans kan deles i mindre instanser av samme problem, blir rekursjon en designmetode i seg selv. Splitt og hersk deler instansen, løser delene rekursivt og kombinerer svarene — og kjøretiden faller ut av en rekurrens som vi kan løse mekanisk.

Metoden: del, hersk, kombiner

Korrektheten følger ved induksjon over instansstørrelsen: grunntilfellene er riktige, og hvis alle de mindre delene blir riktig løst, gjør kombineringssteget resten. Det vi må regne ut, er hvor mye arbeid de rekursive kallene pluss del- og kombineringssteget koster til sammen.

Binærsøk — den enkleste delingen

Binærsøk (Bisect) er det reneste eksempelet: i en sortert tabell sammenligner vi med midtelementet og forkaster den halvdelen som umulig kan inneholde målet. Hvert steg halverer søkevinduet $[lo, hi]$, så vi når fra $n$ til $1$ på $\Theta(\lg n)$ steg.

def binary_search(a: list[int], target: int) -> int:
  lo, hi = 0, len(a) - 1
  while lo <= hi:
      mid = (lo + hi) // 2
      if a[mid] == target:
          return mid
      if a[mid] < target:
          lo = mid + 1
      else:
          hi = mid - 1
  return -1

Binærsøk gir samtidig den enkleste rekurrensen i kurset: ett rekursivt kall på halve instansen pluss konstant arbeid, $T(n) = T(n/2) + \Theta(1) = \Theta(\lg n)$. Den iterative varianten over (while-løkka) er bare den samme rekursjonen rullet ut.

Merge-Sort — balansert deling

Merge-Sort deler tabellen i to like halvdeler, sorterer hver rekursivt og fletter de to sorterte halvdelene med et lineært to-finger-sveip. Delingen er alltid balansert, så vi får $\Theta(\lg n)$ rekursjonsnivåer, og flettingen gjør $\Theta(n)$ arbeid per nivå:

Det gir $\Theta(n \lg n)$ i alle tilfeller — Merge-Sort er ikke følsom for inputrekkefølge. Prisen er $\Theta(n)$ ekstra minne til flettebufferne.

Quicksort — deling ved partisjonering

Quicksort snur problemet: i stedet for å dele blindt på midten og flette etterpå, gjør den alt arbeidet før rekursjonen, ved å partisjonere. Med Lomutos partisjon velger vi pivoten som det høyre elementet, skanner vinduet og samler alt som er $\le$ pivot til venstre. Pivoten havner på sin endelige plass mellom $\le$-regionen og $>$-regionen, og vi sorterer hver side rekursivt — uten noe kombineringssteg.

def quick_sort(a, lo=0, hi=None):
  if hi is None:
      hi = len(a) - 1
  if lo >= hi:
      return
  pivot = a[hi]
  i = lo - 1
  for j in range(lo, hi):
      if a[j] <= pivot:
          i += 1
          a[i], a[j] = a[j], a[i]
  a[i + 1], a[hi] = a[hi], a[i + 1]
  quick_sort(a, lo, i)
  quick_sort(a, i + 2, hi)

Pivotvalget bestemmer alt. Deler partisjonen instansen jevnt, får vi rekurrensen $T(n) = 2T(n/2) + \Theta(n) = \Theta(n \lg n)$, akkurat som Merge-Sort. Men på allerede (omvendt) sortert input lander pivoten i hjørnet hver gang, partisjonen blir maksimalt skjev, og rekurrensen degenererer til $T(n) = T(n-1) + \Theta(n) = \Theta(n^2)$.

Randomisert Quicksort fjerner avhengigheten av inputrekkefølgen ved å velge pivot tilfeldig (eller stokke tabellen først). Da blir den forventede kjøretiden $\Theta(n \lg n)$ for enhver fast input — worst-case finnes fortsatt, men ingen bestemt input kan fremtvinge den. I praksis er Quicksort ofte raskere enn Merge-Sort fordi den sorterer in-place og har små konstantfaktorer.

Å løse rekurrenser

Rekurrensen forteller hvor mye arbeid splitt-og-hersk koster. Tre metoder løser de fleste vi møter:

Standardformen masterteoremet dekker er

der $a \ge 1$ delinstanser hver har størrelse $n/b$ og $f(n)$ er kostnaden for å dele og kombinere. Svaret avgjøres av en kappestrid mellom arbeidet i bladene, $n^{\log_b a}$, og arbeidet på toppen, $f(n)$:

Sjekk deg selv