Referanseside · Kapittel 7

Begreper & formler

Alle nøkkelbegrepene og formlene fra Quicksort, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.

Øv med flashcards8 kort fra dette kapittelet

Begreper

Sentrale begreper fra kapittelet med korte definisjoner.

01Pivot

Elementet valgt for å dele arrayet i mindre og større deler.

02Partisjonering

Prosessen der elementer flyttes slik at de mindre enn pivot ligger til venstre og større til høyre.

03Randomisert quicksort

Velger pivot tilfeldig for å redusere sannsynlighet for verste tilfelle.

04Verste tilfelle

Oppstår når arrayet alltid deles svært skjevt, slik at kjøretid blir $O (n^{2})$ .

05Forventet kjøretid

Gjennomsnittlig kjøretid over alle mulige pivotvalg, vanligvis $O (n lo g n)$ .

Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.

T (n) = T (k) + T (n - k - 1) + Θ (n)

E [T (n)] = Θ (n lo g n)

T (n) = Θ (n^{2})