Splitt og hersk

Del, løs, sett sammen

Tenk deg at du skal telle alle bøkene i et stort bibliotek alene. Det tar evigheter. Men har du femten venner, deler dere lokalet i seksten soner, hver teller sin sone, og til slutt legger dere sammen de seksten tallene. Den siste sammenleggingen er rask; selve tellingen skjedde parallelt og på en brøkdel av tiden. splitt og hersk bygger på akkurat denne ideen, bare at «vennene» er rekursive kall til samme algoritme.

Mønsteret har tre faste steg. Først deler vi problemet i mindre delinstanser av samme type. Så løser vi hver delinstans rekursivt — og fordi de er av samme type, kan vi bruke akkurat den samme algoritmen på dem. Til slutt kombinerer vi delsvarene til et svar på det opprinnelige problemet. Rekursjonen kan ikke fortsette i det uendelige; et basistilfelle er det minste tilfellet vi løser direkte, uten videre splitting. For sortering er en liste med ett element allerede sortert, og det stopper rekursjonen.

Merge-Sort steg for steg

Den reneste illustrasjonen er merge-sort. Den deler arrayet i to like halvdeler, sorterer hver halvdel rekursivt, og fletter de to sorterte halvdelene sammen til ett sortert array. Hele kunsten ligger i flettesteget: når begge halvdeler er sorterte, kan vi flette dem ved å gjentatte ganger plukke det minste av de to fremste elementene.

MERGE-SORT(A, lo, hi):
    if hi - lo <= 1:           # 0 eller 1 element: ferdig sortert
        return
    mid = (lo + hi) // 2
    MERGE-SORT(A, lo, mid)     # venstre halvdel
    MERGE-SORT(A, mid, hi)     # høyre halvdel
    MERGE(A, lo, mid, hi)      # flett de to sorterte halvdelene

Flettingen er lineær: vi går gjennom begge halvdelene én gang, sammenligner de to fremste elementene, og kopierer det minste over i et resultatarray. For to sorterte rekker [2, 5, 8] og [1, 3, 6] plukker vi 1, så 2, så 3, så 5, så 6, så 8 — seks sammenligninger, ett gjennomløp. Med $n$ elementer totalt på et nivå koster flettingen $\Theta (n)$ arbeid.

Det at Merge-Sort alltid deler nøyaktig i to, uansett hvordan dataene ser ut, er grunnen til at den er like rask i beste som i verste tilfelle. Den bryr seg ikke om at inndataene tilfeldigvis er nesten sorterte eller helt baklengs.

Kjøretid som en rekurrens

For å regne ut kjøretiden trenger vi et språk for «tiden for $n$ uttrykt ved tiden for mindre tilfeller». Det språket er en rekurrens: en ligning der $T(n)$ defineres ved $T$ av mindre argumenter. For Merge-Sort er den enkel å lese rett ut av algoritmen — to rekursive kall på halve størrelsen, pluss lineært flettearbeid:

ƒmerge-sort-rekurrensen

Leddet $2T(n/2)$ er de to rekursive kallene, og $\Theta (n)$ er flettingen. Spørsmålet er hva denne rekurrensen løser seg til. Det enkleste er å tegne det opp.

Rekursjonstreet

Et rekursjonstre gjør rekurrensen synlig. Rota er det opprinnelige kallet med kostnad $cn$ for flettingen. Den har to barn, hvert med størrelse $n/2$ og flettekostnad $c\cdot n/2$. To barn à $cn/2$ gir til sammen $cn$ — like mye som rota. Slik fortsetter det: på hvert nivå dobles antall noder, men hver node er halvparten så stor, så summen per nivå holder seg konstant lik $cn$.

Nå er svaret nesten gitt. Hvert nivå koster $cn$. Hvor mange nivåer er det? Vi halverer størrelsen helt ned til 1, og antall halveringer fra $n$ til $1$ er $\lg n$. Med rota teller vi $\lg n+1$ nivåer, hver til $cn$:

$$T(n)=cn\cdot (\lg n+1)=\Theta (n\lg n)$$

Dette er kjernen i hvorfor Merge-Sort er $\Theta (n\lg n)$: konstant arbeid per nivå, logaritmisk mange nivåer.

Substitusjonsmetoden: gjett og bevis

Rekursjonstreet gir intuisjon, men ikke et stramt bevis. Til det bruker vi substitusjonsmetoden: vi gjetter en grense og beviser den med induksjon. Anta vi tror $T(n)\le cn\lg n$ for en passende konstant $c$. Induksjonssteget setter den antatte grensen inn for de mindre tilfellene på høyresiden:

$$T(n)\le 2\left(c\cdot \frac{n}{2}\lg \frac{n}{2}\right)+dn=cn\lg n-cn+dn.$$

Så lenge $c\ge d$ er $-cn+dn\le 0$, og hele uttrykket er $\le cn\lg n$. Induksjonen går opp, og gjettet er bekreftet. Substitusjon krever altså at du har en kandidat på forhånd — derfor er rekursjonstreet en så nyttig forløper: det produserer gjettet du senere beviser.

Masterteoremet: en kokebok

De fleste splitt-og-hersk-rekurrenser har samme form: $a$ delinstanser av størrelse $n/b$ pluss kombinasjonskostnad $f(n)$. masterteoremet er en oppskrift som leser av svaret direkte fra disse tre tallene, uten at du tegner tre eller kjører induksjon:

ƒmasterteoremet

Hele avgjørelsen står og faller på en sammenligning mellom kombinasjonsarbeidet $f(n)$ og uttrykket $n^{{\log }_{b}a}$. Det siste tallet teller hvor mye arbeid løvene i rekursjonstreet utgjør til sammen. Tre utfall er mulige.

I tilfelle 1 vokser $f(n)$ polynomielt saktere enn løvene. Da dominerer bladene, og svaret styres av dem:

ƒmasterteoremet, tilfelle 1

I tilfelle 2 er kombinasjon og blader i balanse — like mye arbeid på hvert nivå, akkurat som i Merge-Sort. Hvert av de ${\log }_{b}n$ nivåene bidrar likt, og vi får en ekstra logaritmisk faktor:

ƒmasterteoremet, tilfelle 2

For Merge-Sort er $a=2$, $b=2$ og $f(n)=\Theta (n)$. Da er $n^{{\log }_{b}a}=n^{{\log }_{2}2}=n^1=n$, som matcher $f(n)$ — tilfelle 2 treffer, og svaret er $\Theta (n\lg n)$. Samme svar som rekursjonstreet ga, på sekunder.

I tilfelle 3 vokser kombinasjonsarbeidet polynomielt raskere enn løvene, og (med en mild regularitetsbetingelse) dominerer rota:

ƒmasterteoremet, tilfelle 3

Masterteoremet dekker ikke alle rekurrenser — det krever fast forhold mellom $f(n)$ og $n^{{\log }_{b}a}$, og noen rekurrenser faller i sprekkene mellom tilfellene. Da må du tilbake til rekursjonstre eller substitusjon. Men for det store flertallet av splitt-og-hersk-algoritmer er det den raskeste veien til svaret.

Quicksort: rask i snitt, treg i verste fall

quicksort er den andre store splitt-og-hersk-sorteringen, og den jobber annerledes enn Merge-Sort. Den velger et pivot-element og partisjonerer arrayet: alt mindre enn pivoten havner til venstre, alt større til høyre. Så sorterer den de to sidene rekursivt. Det fine er at all jobbingen skjer i partisjoneringen, før de rekursive kallene — det finnes ikke noe eget flettesteg, og sorteringen skjer på stedet.

QUICKSORT(A, lo, hi):
    if hi - lo <= 1:
        return
    p = PARTITION(A, lo, hi)   # plasser ett element riktig, del rundt det
    QUICKSORT(A, lo, p)        # venstre del (mindre enn pivot)
    QUICKSORT(A, p + 1, hi)    # høyre del (større enn pivot)

Kjøretiden avhenger helt av hvor balanserte partisjonene blir. Velger vi alltid et pivot som lander midt i, deler vi i to like halvdeler hver gang, og rekurrensen blir den samme som Merge-Sort — $\Theta (n\lg n)$. Men velger vi et uheldig pivot som lar den ene siden være tom, går det galt:

ƒquicksort, verste tilfelle

Da blir rekursjonsdybden $n$ i stedet for $\lg n$, og kostnadene danner en aritmetisk rekke $cn+c(n-1)+\cdots +c$, som summerer til $\Theta (n^2)$. Et eksempel: sorterer du et allerede sortert array og velger alltid det første elementet som pivot, treffer du nettopp dette verste tilfellet hver gang.

Løsningen er enkel og elegant: velg pivot tilfeldig. Da blir det praktisk talt umulig for inndataene å fremtvinge skjeve splitter gjentatte ganger, fordi rekkefølgen i arrayet ikke lenger styrer pivotvalget. Forventet kjøretid blir like god som Merge-Sort:

ƒquicksort, forventet kjøretid

I praksis er Quicksort ofte raskere enn Merge-Sort til tross for samme asymptotiske kjøretid, fordi den sorterer på stedet og har små konstantfaktorer. Det er en god påminnelse om at $\Theta (n\lg n)$ ikke er ett enkelt tall — to algoritmer med samme asymptotiske klasse kan likevel ha merkbart ulik fart på ekte data.