Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Verktøykassa: notasjon og forkunnskaper, 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.
Taket runder opp til nærmeste heltall, gulvet runder ned. Brukes når vi deler noe i (nesten) like store deler.
er eksponenten slik at . I algoritmer bruker vi mest tobaselogaritmen , som teller halveringer.
er resten når deles på . Sentralt i hashing og når indekser skal pakkes inn i et fast intervall.
En uordnet samling distinkte elementer. Grunnlaget for å snakke om noder, kanter og delmengder presist.
Et par av noder og kanter som modellerer relasjoner. Kan være rettet eller urettet, vektet eller uvektet.
Antall kanter som møter en node. I rettede grafer skiller vi inn-grad og ut-grad.
En sammenhengende blokk minne med konstant-tids tilgang via indeks, men dyr innsetting midt i.
En sekvens av noder der hver peker på den neste. Billig innsetting/sletting, men lineært oppslag.
En struktur som gir forventet konstant-tids oppslag, innsetting og sletting ved å spre nøkler over bøtter med en hashfunksjon.
Strategi der et dynamisk array dobler kapasiteten når det blir fullt, slik at innsetting blir amortisert konstant.
En spesifikasjon av hvilke operasjoner en struktur tilbyr, uavhengig av hvordan den er implementert — for eksempel en kø eller en prioritetskø.
Produktet av alle heltall fra 1 til , skrevet . Teller antall måter å ordne ting på, og vokser raskere enn enhver eksponentialfunksjon.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Gulv og tak
Gulvet runder nedover til nærmeste heltall, taket oppover. For et heltall er de like. De dukker opp hver gang noe deles i (nesten) like store halvdeler.
Aritmetisk sum (håndtrykk)
Summen av de første heltallene. Forklarer hvorfor doble løkker der den indre teller opp mot den ytre koster .
Geometrisk sum
Dominert av det største leddet når . Forklarer hvorfor totalkostnaden ved tabelldobling forblir lineær.
Logaritmeregler
Logaritmer gjør multiplikasjon til addisjon, og basebytte er bare en konstant faktor. Derfor skriver vi gjerne uten å bry oss om basen i -notasjon.
Modulo
Resten ved heltallsdivisjon. Brukes til å pakke indekser inn i et fast intervall, blant annet i hashfunksjoner.
Håndtrykkslemma
I en urettet graf teller hver kant to ganger i gradsummen — én gang for hver ende. Derfor er gradsummen alltid et partall.
Maks antall kanter
En enkel urettet graf uten løkker eller parallelle kanter har høyst denne kantmengden. Tette grafer nærmer seg grensa, glisne grafer er langt under.
Amortisert kostnad ved tabelldobling
Selv om enkelte innsettinger i et dynamisk array koster når tabellen dobles, blir gjennomsnittet per innsetting konstant fordi doblingene blir stadig sjeldnere.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Bruke tak, gulv og modulo til å dele en mengde i nesten like deler og pakke indekser inn i et fast intervall
- 02Tolke en toerlogaritme som antall halveringer, og forklare hvorfor basen er likegyldig i kjøretidsanalyse
- 03Gjenkjenne den aritmetiske og den geometriske summen, og koble dem til kjøretiden til nøstede løkker og tabelldobling
- 04Forklare avveiningene mellom array, lenket liste og hashtabell, og hvorfor tabelldobling gir amortisert konstant innsetting