Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Algoritmer, kjøretid og asymptotisk notasjon, 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 endelig, presis oppskrift som transformerer inndata til ønsket utdata på et endelig antall steg.
En idealisert maskinmodell der grunnleggende operasjoner (aritmetikk, sammenligning, minnetilgang) koster konstant tid.
Beskriver hvordan kjøretiden vokser når inndata blir stor, og ignorerer konstanter og lavordens-ledd.
En asymptotisk øvre grense: betyr at til slutt vokser høyst like raskt som , opp til en konstant.
En asymptotisk nedre grense: betyr at til slutt vokser minst like raskt som .
En tett grense: betyr at vokser nøyaktig like raskt som — både og samtidig.
Kjøretiden over henholdsvis den gunstigste inndataen, den verste, og forventningen over en fordeling. Gjennomsnittet er ikke nødvendigvis snittet av beste og verste.
En påstand som er sann før løkka starter og bevares av hver iterasjon, brukt til å bevise at en algoritme er korrekt.
En enkel sortering som setter hvert element inn på riktig plass blant de allerede sorterte. i verste fall, i beste.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Store O (øvre grense)
vokser ikke raskere enn utover en konstant faktor, fra et punkt og utover. Beskriver en øvre grense på kjøretiden.
Store Omega (nedre grense)
vokser minst like raskt som utover en konstant faktor. Beskriver en nedre grense på kjøretiden.
Store Theta (tett grense)
er både og , altså av nøyaktig samme vekstorden som . Den sterkeste og mest presise påstanden.
Insertion-Sort, verste tilfelle
Med en synkende sortert inndata må hvert nytt element flyttes forbi alle de foregående — totalt en aritmetisk sum av forskyvninger.
Insertion-Sort, beste tilfelle
En allerede sortert inndata krever bare én sammenligning per element; ingen forskyvninger. Viser hvorfor beste tilfelle ikke trenger å være som verste.
Sum av polynom
En generell regel som forklarer kjøretiden til nøstede løkker: nøstede løkker som teller opp til gir -arbeid.
Transitivitet for O
Asymptotiske grenser oppfører seg som ulikheter: de kan lenkes sammen. Gjelder tilsvarende for og .
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Forklare hva RAM-modellen idealiserer, og hvorfor vi teller grunnoperasjoner i stedet for sekunder
- 02Skille mellom O, Omega og Theta som øvre, nedre og tett grense, og velge riktig påstand
- 03Spore Insertion-Sort på et eksempel og begrunne hvorfor verste tilfelle er Theta(n^2) og beste er Theta(n)
- 04Formulere en løkkeinvariant og bruke oppstart–bevaring–avslutning til å argumentere for at en løkke er korrekt