Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Splitt og hersk, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
En metode som deler problemet i mindre delinstanser, løser dem rekursivt, og kombinerer delsvarene.
En ligning som uttrykker kjøretiden for størrelse n i form av kjøretiden for mindre størrelser.
Det minste tilfellet som løses direkte uten videre rekursjon — det som stopper rekursjonen.
Å gjette en grense for rekurrensen og bevise den med induksjon.
En visualisering der hver node er kostnaden av et rekursivt kall; summen over alle nivåer gir kjøretiden.
En kokebok-formel som løser rekurrenser på formen ved å sammenligne med .
Splitter arrayet i to, sorterer hver halvdel rekursivt, og fletter dem sammen. i alle tilfeller.
Partisjonerer rundt et pivotelement og sorterer delene rekursivt. Forventet , men i verste fall.
Elementet Quicksort partisjonerer rundt. Et tilfeldig valgt pivot gjør verste tilfelle svært usannsynlig.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Merge-Sort-rekurrensen
To delinstanser av halv størrelse, pluss lineært arbeid for å flette dem sammen. Løser seg til .
Masterteoremet
Standardformen for splitt-og-hersk-rekurrenser: delinstanser av størrelse og kombinasjonskostnad . Tre tilfeller avgjør svaret.
Masterteoremet, tilfelle 1
Når kombinasjonsarbeidet vokser polynomielt saktere enn løvene, dominerer rekursjonstreets blader.
Masterteoremet, tilfelle 2
Når kombinasjon og blader er balansert, bidrar hvert nivå like mye, og vi får en ekstra -faktor for antall nivåer.
Masterteoremet, tilfelle 3
Når kombinasjonsarbeidet vokser polynomielt raskere (og regularitetsbetingelsen holder), dominerer rota.
Quicksort, verste tilfelle
Et helt skjevt pivotvalg lar den ene delen være tom hver gang, så rekursjonsdybden blir . Tilfeldig pivot gjør dette svært usannsynlig.
Quicksort, forventet kjøretid
Med randomisert pivot er splittene balanserte i gjennomsnitt, og forventet kjøretid blir like god som Merge-Sort.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Beskrive de tre stegene i splitt og hersk og forklare hva basistilfellet gjør i en rekursiv algoritme
- 02Sette opp rekurrensen for Merge-Sort og bruke et rekursjonstre til å vise at den løser seg til Θ(n lg n)
- 03Anvende masterteoremet på en rekurrens T(n)=aT(n/b)+f(n) ved å sammenligne f(n) med n^{log_b a} og velge riktig tilfelle
- 04Forklare hvorfor Quicksort er Θ(n²) i verste fall men forventet Θ(n lg n), og hvordan tilfeldig pivot unngår verste tilfelle