3.5 Køer, stakker, amortisert analyse og disjunkte mengder

FIFO-kø med wraparound (håndkjøring), stakk (LIFO), `Table-Insert` (amortisert `O(1)`) og disjunkte mengder (`Union-Find`) — de øvrige strukturene.

55 min

8 oppgaver

Køerstakkeramortisert analysedisjunkte mengder

Din fremgang i kapitlet

0 / 8 oppgaver

Kapitlets plass i kurset

Bygger på

3.1Hauger og Heapsort

Brukes videre i

3.PPrøver til del 3: Datastrukturer: hauger, søketrær og hashing 4.1Grafrepresentasjon, traversering og topologisk sortering

Køer og stakker er registrert i 5 av de 17 settene i grunnlaget (29 %), og
amortisert analyse og disjunkte mengder i like mange, 5 av 17 (29 %).
Grunnlaget er de 17 settene fra august 2015 til august 2023 som er gjennomgått
tema for tema — det er nevneren hver gang boka oppgir en prosent.

Prioritet: kjenne til. Men det er en «kjenne til» med en viktig
presisering — de tre delene av kapitlet har helt ulik rolle:

- Kø-håndkjøringen er en ren mekanisk oppgave du enten får til eller ikke.
Den koster fem minutter å lære, og den kommer i sjanger C — håndkjøring,
altså at du utfører operasjonene steg for steg og oppgir sluttilstanden.
Svarformen er hele tabellen, inkludert de «døde» cellene, pluss head
og tail.
- Amortisert analyse kommer i sjanger D — definisjon med egne ord og
E — kjøretidskunnskap. Du skal kunne si hva ordet betyr og hvorfor
dobling gir amortisert $O(1)$ .
- Union-Find er verktøyet i MST-Kruskal i
kap. 4.2. Det er den viktigste grunnen til at det
står her: uten disjunkte mengder er Kruskals syklustest en gåte.

Slik er kapitlet lagt opp (55 min):

Innhold	Tid
FIFO-køen, wraparound og de døde cellene	ca. 16 min
Stakken	ca. 7 min
Amortisert analyse og `Table-Insert`	ca. 15 min
Disjunkte mengder og `Union-Find`	ca. 17 min

— naturlig pausepunkt — etter stakken. De to siste delene henger ikke sammen
med de to første og kan tas i en egen økt.

Forkunnskaper

- kap. 3.1 — hauger. Dette sto der: en datastruktur kan
bo i et array A[1..n] med indeks fra 1, og operasjonene beskrives som
indeksregning. Vi bruker den samme konvensjonen her.
- kap. 1.1 — de asymptotiske symbolene. Amortisert
analyse handler om å skille kostnaden til én operasjon fra
gjennomsnittet over en hel serie, og det krever presis notasjon.
- kap. 2.1 — «forventet» mot «garantert». Amortisert er
en tredje ting igjen: det er et gjennomsnitt over en serie operasjoner, uten
noen sannsynlighet inne i bildet.

Ingen av delene krever noe utover dette.

Notasjons- og pseudokodeliste

FIFO-køen, wraparound og de døde cellene (~16 min)

I kantinekøen står den som kom først, fremst. Nye gjester stiller seg bakerst,
og det er alltid den fremste som blir betjent. Det er en FIFO-kø — first
in, first out.

Skal køen ligge i et array med fast lengde, oppstår et praktisk problem. Etter
noen inn- og utmeldinger har hele køen «vandret» bakover i arrayet, og til slutt
er den bakerste plassen brukt opp — selv om det er masse ledig plass foran.
Løsningen er å la køen gå rundt hjørnet: når indeksen når enden, begynner
den på 1 igjen. Det kalles wraparound, og det er derfor køen kalles
sirkulær.

FIFO-kø

\Theta(1)

`head` og `tail`

Q.head er indeksen til det fremste elementet, altså det som tas ut ved neste Dequeue . Q.tail er indeksen der det neste elementet skal skrives inn. Køen er tom når head == tail, og den inneholder elementene fra head og rundt til, men ikke med, tail . Å bytte om de to er den vanligste feilen i denne håndkjøringen. Huskeregel: head er der du spiser fra, tail er der du legger på .

Wraparound og døde celler

Wraparound er regelen om at en indeks som når n, settes til 1 ved neste økning — arrayet leses som en sirkel. En død celle er en celle som ligger utenfor det logiske intervallet fra head til tail, men som fortsatt inneholder en gammel verdi. Dequeue sletter ikke noe; den flytter bare head . Døde celler skal med i svaret. Svarformatet for en kø-håndkjøring er hele tabellen slik den faktisk står i minnet, pluss head og tail .

📜Pseudokode-kontrakt: `Enqueue` og `Dequeue`

Antagelser om representasjon. Køen ligger i Q[1..n], indeks fra 1. Ved
oppstart er Q.head = Q.tail = 1. Cellene som ikke er i bruk, beholder de
verdiene de måtte ha fra før — ingenting nullstilles.

Prebetingelse: for Enqueue at køen ikke er full; for Dequeue at den
ikke er tom.
Postbetingelse: Enqueue har lagt x bakerst; Dequeue har returnert det
fremste elementet og flyttet head.

Enqueue(Q, x)
  Input:  koeen Q og et element x
  Output: x lagt bakerst i koeen
  Q[Q.tail] = x
  if Q.tail == Q.length
      Q.tail = 1
  else
      Q.tail = Q.tail + 1

Dequeue(Q)
  Input:  koeen Q
  Output: det fremste elementet
  x = Q[Q.head]
  if Q.head == Q.length
      Q.head = 1
  else
      Q.head = Q.head + 1
  return x
  Kjoeretid: Theta(1) for begge

Invarianten i én setning: de elementene som faktisk står i køen, er de som
ligger fra indeks head og framover — rundt hjørnet om nødvendig — til, men
ikke med, indeks tail.

Legg merke til at Dequeue ikke sletter noe. Verdien blir liggende igjen i
cellen, og den kan bli overskrevet senere av en Enqueue som kommer rundt.
Det er nettopp disse restene som er de døde cellene.

Kjøretid: $\Theta(1)$ for begge — noen få indeksregninger, uansett hvor
mange elementer køen inneholder.

✏️Eksempel 1: Ni operasjoner på en kø med fem plasser

En vaktsentral bruker en sirkulær FIFO-kø Q[1..5] til innkommende meldinger.
Ved oppstart er Q.head = Q.tail = 1, og alle cellene er tomme.

Utfør: Enqueue(a), Enqueue(b), Enqueue(c), Enqueue(d), Dequeue,
Dequeue, Dequeue, Enqueue(e), Enqueue(f).

Oppgi hele tabellen til slutt, sammen med head og tail.

En understrek betyr at cellen aldri har vært skrevet i.

Steg	Operasjon	Hva som skjer	`Q[1..5]` etterpå	`head`	`tail`
1	`Enqueue(a)`	skriver a i Q[1]	`a, _, _, _, _`	1	2
2	`Enqueue(b)`	skriver b i Q[2]	`a, b, _, _, _`	1	3
3	`Enqueue(c)`	skriver c i Q[3]	`a, b, c, _, _`	1	4
4	`Enqueue(d)`	skriver d i Q[4]	`a, b, c, d, _`	1	5
5	`Dequeue`	returnerer a fra Q[1]	`a, b, c, d, _`	2	5
6	`Dequeue`	returnerer b fra Q[2]	`a, b, c, d, _`	3	5
7	`Dequeue`	returnerer c fra Q[3]	`a, b, c, d, _`	4	5
8	`Enqueue(e)`	skriver e i Q[5]	`a, b, c, d, e`	4	1
9	`Enqueue(f)`	skriver f i Q[1]	`f, b, c, d, e`	4	2

Sluttilstanden — det du ville levert på eksamen:
Tabell: f, b, c, d, e, head = 4,
tail = 2.
Tre ting er verdt å studere i tavlen.
For det første: de tre Dequeue-operasjonene endrer ikke tabellen i det
hele tatt. Bare head flytter seg. Verdiene a, b og c blir liggende.
For det andre: steg 8 skriver e i Q[5], og siden tail da sto på 5, går
den rundt hjørnet til 1. Steg 9 skriver derfor f over den døde verdien a.
For det tredje: den logiske køen til slutt er
d, e, f — les fra head = 4

og rundt til tail = 2. Men b og c står fortsatt i

tabellen som døde celler, og de skal med i svaret.
Fellen her er #3 — køfeil ved håndkjøring: å levere bare den logiske køen

d, e, f i stedet for hele tabellen, eller å bytte

om head og tail. Delvis riktig svar gir delvis uttelling, og det siste
poenget henger på at både tabellen og begge indeksene er med.

📝Oppgave 1

(Innstegsoppgave, sjanger D — definisjon med egne ord, altså én presis setning
med hovedpoenget først.)

Forklar hva head og tail peker på i en sirkulær FIFO-kø, og hva som menes
med en «død celle».

📝Oppgave 2

Eksamensnivå, sjanger C

En sirkulær FIFO-kø Q[1..4] starter tom med head = tail = 1.

Utfør: Enqueue(p), Enqueue(q), Dequeue, Enqueue(r), Enqueue(s),
Dequeue, Enqueue(t).

Oppgi hele tabellen, head og tail.

📝Oppgave 3

Eksamensnivå, sjanger F

Ta stilling til hver av påstandene om en sirkulær FIFO-kø Q[1..n]:

a) Køen er tom når head == tail.
b) Dequeue nullstiller cellen den leser fra.
c) Enqueue og Dequeue er $O(\lg n)$ .

Stakken (~7 min)

Stakken er køens speilbilde. Der køen tar ut det eldste, tar stakken ut det
nyeste — som en bunke tallerkener der du både legger på og tar av på toppen.

📜Pseudokode-kontrakt: `Push` og `Pop`

Antagelser om representasjon. Stakken ligger i S[1..n], indeks fra 1.
S.top er indeksen til det øverste elementet, og S.top = 0 betyr tom stakk.

Prebetingelse: for Push at stakken ikke er full; for Pop at den ikke er
tom.
Postbetingelse: Push har lagt x øverst; Pop har returnert og fjernet
det øverste elementet.

Push(S, x)
  Input:  stakken S og et element x
  Output: x lagt oeverst
  S.top = S.top + 1
  S[S.top] = x

Pop(S)
  Input:  stakken S
  Output: det oeverste elementet
  S.top = S.top - 1
  return S[S.top + 1]
  Kjoeretid: Theta(1) for begge

Invarianten i én setning: elementene i stakken er S[1..S.top], med det
sist innlagte øverst.

Ingen wraparound trengs. Stakken vokser og krymper i samme ende, så den
vandrer aldri gjennom arrayet slik køen gjør. Det er derfor
stakk-håndkjøringer er enklere enn kø-håndkjøringer — og derfor køen er den
som kommer på eksamen.

Kjøretid: $\Theta(1)$ for begge.

📝Oppgave 4

Sjanger C

En stakk S[1..5] starter tom med S.top = 0.

Utfør: Push(4), Push(9), Push(2), Pop, Push(7), Pop, Push(5).

Oppgi S[1..S.top] og verdien til S.top til slutt, samt hvilke verdier
Pop returnerte.

Amortisert analyse og `Table-Insert` (~15 min)

En dynamisk tabell er et array som vokser etter behov. Så lenge det er plass,
koster en innsetting konstant tid. Blir tabellen full, må den byttes ut med en
dobbelt så stor, og alt kopieres over — en enkeltoperasjon som koster
$\Theta(n)$ .

Spørsmålet er hva en innsetting «koster» når noen få av dem er så dyre. Svaret
er ikke verste tilfelle for én operasjon, og det er heller ikke et
sannsynlighetsregnestykke. Det er en tredje ting: amortisert kostnad.

Amortisert kjøretid

O(1)

📜Pseudokode-kontrakt: `Table-Insert`

Antagelser om representasjon. Tabellen T har feltene T.num (antall
elementer) og T.size (kapasitet). Ved oppstart er begge 0. Å allokere en ny
tabell og kopiere over T.num elementer koster

\Theta(T.num)

Prebetingelse: ingen.
Postbetingelse: x ligger i tabellen, og T.num er økt med 1.

Table-Insert(T, x)
  Input:  den dynamiske tabellen T og et element x
  Output: T med x satt inn
  if T.size == 0
      alloker T med plass til 1 element
      T.size = 1
  if T.num == T.size
      alloker en ny tabell med plass til 2 * T.size
      kopier alle T.num elementer over
      T.size = 2 * T.size
  sett x inn i T
  T.num = T.num + 1
  Kjoeretid: Theta(n) i verste tilfelle, amortisert O(1)

Grunnideen i én setning: en dobling er dyr, men den kjøper plass til like
mange billige innsettinger som det nettopp ble kopiert elementer — så
kostnaden fordeles utover.

Utledningen, ledd for ledd. Kopieringer skjer ved innsetting nummer $1, 2, 4, 8, \dots$ , altså ved hver toerpotens opp til $n$ .

Intuisjon: det er de eneste øyeblikkene tabellen er full.

Kopieringen ved innsetting nummer $2^j$ koster $2^{j-1}$ (antall elementer som
flyttes). Summen av alle kopieringene er derfor

$1 + 2 + 4 + \dots + 2^{\lfloor \lg n\rfloor} < 2n$

Intuisjon: den geometriske summen domineres av det siste leddet — all
kopiering til sammen koster mindre enn to ganger den siste kopieringen. Det er
den samme egenskapen som gjør at $1 + \tfrac12 + \tfrac14 + \dots < 2$ .

I tillegg koster hver av de $n$ innsettingene selv $\Theta(1)$ . Totalen blir
under $3n$ , altså $O(n)$ .

Intuisjon: deler du $O(n)$ på $n$ operasjoner, får du $O(1)$ per operasjon.

Kjøretid: $\Theta(n)$ i verste tilfelle for én innsetting, men
amortisert $O(1)$ over en serie.

✏️Eksempel 2: Kostnaden for de seksten første innsettingene

En dynamisk tabell starter tom. Sett inn seksten elementer med Table-Insert,
og regn ut kostnaden per innsetting og totalen.

Kostnaden for en innsetting er 1 hvis det er plass, og $1 +$ antall elementer
som må kopieres hvis tabellen må dobles.

Innsetting nr.	Kapasitet etterpå	Kostnad	Sum så langt
1	1	1	1
2	2	2	3
3	4	3	6
4	4	1	7
5	8	5	12
6	8	1	13
7	8	1	14
8	8	1	15
9	16	9	24
10	16	1	25
11	16	1	26
12	16	1	27
13	16	1	28
14	16	1	29
15	16	1	30
16	16	1	31

Totalen for 16 innsettinger: 31 enheter, altså
1,94 per innsetting i snitt.
Det avgjørende er at snittet ikke vokser. De dyre radene er få og ligger
langt fra hverandre: 1, 2, 3, 5, 9, 17 og så videre — én for hver toerpotens.
Mellom dem ligger stadig lengre strekk med kostnad 1.
Regn etter: kopieringene koster

1 + 2 + 4 + 8 = 15

til sammen, altså under

2n = 32

. Legger vi til de 16 enkeltinnsettingene og de to første
allokeringene, ender vi under

3n = 48

.
Svarformen på eksamen: «amortisert

O(1)

, fordi doblingene koster under

2n

til sammen». To linjer. Ikke hele tabellen, med mindre den er etterspurt.

📝Oppgave 5

Eksamensnivå, sjanger F

En kandidat skriver: «Table-Insert er $\Theta(n)$ per innsetting, siden
tabellen må kopieres.»

Er utsagnet riktig? Svar ja eller nei, og gi den presise formuleringen.

📝Oppgave 6

Eksamensnivå, sjanger F…

En kollega foreslår å la tabellen vokse med ett element om gangen i stedet
for å doble: hver gang den er full, allokeres en ny tabell med plass til
T.size + 1 elementer.

a) Hva blir den totale kostnaden for $n$ innsettinger?
b) Hva blir den amortiserte kostnaden per innsetting?
c) Hva er lærdommen?

Disjunkte mengder og `Union-Find` (~17 min)

Et veinett bygges ut bit for bit. Etter hver nye veistrekning vil du vite: er
disse to stedene nå knyttet sammen, direkte eller indirekte? Og: hører disse to
til samme sammenhengende område?

Strukturen som svarer på slike spørsmål heter disjunkte mengder, ofte kalt
Union-Find. Den holder styr på en samling mengder som ikke overlapper, og
støtter to ting: slå sammen to mengder, og finne ut hvilken mengde et element
hører til.

Det er nøyaktig det MST-Kruskal trenger i kap. 4.2:
en kant kan legges til spenntreet bare hvis endepunktene ligger i ulike
komponenter.

Disjunkte mengder

en samling mengder der ingen to mengder har noe element felles. Hver mengde har en utpekt representant — ett bestemt element som står for hele mengden. To elementer ligger i samme mengde nøyaktig når Find-Set gir samme representant for begge. Representanten kan skifte når to mengder slås sammen, men så lenge ingenting endres, er den den samme hver gang du spør.

Skogrepresentasjonen

hver mengde lagres som et tre : hver node har en peker x.p til forelderen, og rota peker på seg selv. Rota er mengdens representant. Find-Set(x) følger p -pekerne oppover til den når rota. Trærne her har ingenting med søketrær å gjøre. Det finnes ingen ordning mellom nodene — pekerne sier bare «tilhører samme mengde som».

Rangheuristikken

O(\lg n)

📜Pseudokode-kontrakt: `Make-Set`, `Find-Set`, `Union` og `Link`

Antagelser om representasjon. Hvert element x har feltene x.p
(forelder) og x.rank. Rota r har r.p = r. Denne boka bruker
rangheuristikken, men ikke stikomprimering.

Prebetingelse: for Make-Set at x ikke allerede ligger i en mengde; for
Union at begge argumentene ligger i en mengde.
Postbetingelse: Find-Set(x) returnerer representanten for mengden x
ligger i. Union(x, y) gjør at x og y etterpå ligger i samme mengde.

Make-Set(x)
  x.p = x
  x.rank = 0

Find-Set(x)
  while x.p != x
      x = x.p
  return x

Link(x, y)
  Input:  to ROETTER x og y
  if x.rank > y.rank
      y.p = x
  else
      x.p = y
      if x.rank == y.rank
          y.rank = y.rank + 1

Union(x, y)
  Link(Find-Set(x), Find-Set(y))
  Kjoeretid: Theta(1) for Make-Set, O(lg n) for Find-Set og Union

Invarianten i én setning: hver mengde er et tre der alle p-pekere fører
opp til representanten, og x.rank er alltid minst like stor som høyden på
deltreet under x.

Legg merke til at Link tar to røtter, ikke to vilkårlige elementer.
Union gjør oppslaget først. En vanlig håndkjøringsfeil er å henge et element
midt i treet under en annen rot.

Kjøretid: Make-Set er $\Theta(1)$ . Find-Set følger én sti opp til rota,
og med rangheuristikken er høyden $O(\lg n)$ — derav $O(\lg n)$ for både
Find-Set og Union.

✏️Eksempel 3: Fire sammenslåinger med rangheuristikk

Seks målestasjoner a, b, c, d, e, f starter hver for seg:
Make-Set kalles på alle seks, så alle har rang 0 og er sin egen rot.

Utfør Union(a, b), Union(c, d), Union(b, d) og Union(e, f).

Oppgi hvilke mengder som finnes til slutt, hvem som er representant for hver,
og hva Find-Set(a) returnerer.

Steg	Operasjon	Hva som skjer	Mengdene etterpå
1	`Union(a, b)`	like ranger (0): rot a henges under rot b, og b får rang 1	{a, b} med rot b; {c} med rot c; {d} med rot d; {e} med rot e; {f} med rot f
2	`Union(c, d)`	like ranger (0): rot c henges under rot d, og d får rang 1	{a, b} med rot b; {c, d} med rot d; {e} med rot e; {f} med rot f
3	`Union(b, d)`	like ranger (1): rot b henges under rot d, og d får rang 2	{a, b, c, d} med rot d; {e} med rot e; {f} med rot f
4	`Union(e, f)`	like ranger (0): rot e henges under rot f, og f får rang 1	{a, b, c, d} med rot d; {e, f} med rot f

Sluttilstanden — det du ville levert på eksamen:
Mengdene er {a, b, c, d} med representant d, og {e, f} med representant
f. Find-Set(a) returnerer d.
Slik ser skogen ut:

        d (rang 2)                f (rang 1)
       /         \                   |
   b (rang 1)  c (rang 0)        e (rang 0)
      |
   a (rang 0)

Legg merke til hvordan rangene styrer. I steg 1 og 2 møtes to røtter med

rang 0, og den ene får rang 1. I steg 3 møtes to røtter med rang 1 — igjen
uavgjort, så den ene blir rot og får rang 2. Hadde rangene vært ulike, ville

den lavere rota alltid havnet under, og ingen rang ville økt.

Find-Set(a) følger to pekere: fra a til b, fra b til d. Det er

høyden på treet, og det er nettopp den rangheuristikken holder nede.

📝Oppgave 7

Eksamensnivå, sjanger C

Fem noder u, v, w, x, y får hver sin Make-Set.

Utfør Union(u, v), Union(w, x), Union(v, w), Union(x, y).

a) Hvilke mengder finnes til slutt, og hvem er representanten?
b) Hvor mange pekere følger Find-Set(u)?

📝Oppgave 8

Eksamensnivå, sjanger H

Et fiberselskap legger nye kabler mellom $n$ kundesteder, én strekning om
gangen, til sammen $m$ strekninger. Etter hver ny strekning vil de vite hvor
mange sammenhengende områder nettet består av.

Beskriv en algoritme, og oppgi kjøretiden.

Typiske feil

De to første koster hele oppgaven.

- Å levere bare den logiske køen. Dette er felle #3 — køfeil ved
håndkjøring. Svarformatet er hele tabellen Q[1..n] inkludert de døde
cellene, pluss head og tail. Dequeue sletter ingenting.
- Å bytte om head og tail. Også felle #3. head er der du tar ut,
tail er der du legger på. Delvis riktig svar gir delvis uttelling, men
ombytting gir feil i hele tabellen.
- Å glemme wraparound. Når tail står på n og en Enqueue kommer, skal
tail bli 1 — ikke n+1. Det er samme regel for head.
- Å oppgi Table-Insert som $\Theta(n)$ per innsetting. Det er verste
tilfelle for én operasjon; amortisert er den $O(1)$ . Begge tallene er
riktige, og fellen er å oppgi det ene der det andre er etterspurt.
- Å blande amortisert med forventet. Amortisert er et gjennomsnitt over en
serie, i verste tilfelle for serien — uten noen sannsynlighet. «Forventet»
er et gjennomsnitt over tilfeldige valg.
- Å henge et ikke-rot-element under en rot i Union. Link tar to
røtter. Kall Find-Set på begge argumentene først.
- Å øke rangen når rangene er ulike. Rangen økes bare når to røtter med
lik rang møtes.
- Å tro at Union-Find-trærne er søketrær. Det finnes ingen ordning mellom
nodene; pekerne betyr bare «samme mengde».

Og den gjennomgående: å oppgi mer enn det som er spurt om. Ber oppgaven om
head og tail, er to tall svaret.

Kjøretidene samlet

Dette er kapitlets puggeflate. Eksamen er hjelpemiddelfri, så tabellen må ligge
i hodet.

Operasjon	Kjøretid	Krav / egenskap
`Enqueue`, `Dequeue`	$\Theta(1)$	sirkulært array; `Dequeue` sletter ikke, den flytter `head`
`Push`, `Pop`	$\Theta(1)$	LIFO; ingen wraparound nødvendig
`Table-Insert`	$\Theta(n)$ verste for én, amortisert $O(1)$	doblingsstrategi; fast økning gir amortisert $\Theta(n)$
`Make-Set`	$\Theta(1)$	oppretter et enkeltnode-tre med rang 0
`Find-Set`	$O(\lg n)$	med rangheuristikk; følger én sti opp til rota
`Union`	$O(\lg n)$	to `Find-Set` pluss ett `Link`
$n$ `Table-Insert` til sammen	$O(n)$	dette er hele poenget med «amortisert»

Én presisering som er verdt å ta med seg. De tre delene av dette kapitlet
har hver sin rolle på eksamen: køen kommer som håndkjøring, amortisert analyse
som definisjon, og Union-Find som verktøy i MST-Kruskal. Ingen av dem er
tunge, men alle tre har en presis svarform.

Begrepsbank

Begrepsbanken er flashcard- og repetisjonsstoff — den gjentar det du nettopp
har lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet
gjelder kjernestoffet.

FIFO-kø

\Theta(1)

Stakk

\Theta(1)

`head` og `tail`

head er indeksen til det fremste elementet i køen; tail er indeksen der neste element skal skrives. Køen er tom når head == tail . Å bytte om de to er den vanligste håndkjøringsfeilen i denne strukturen — felle #3.

Wraparound

regelen om at en indeks som når n, settes til 1 ved neste økning, slik at arrayet leses som en sirkel. Gjelder både head og tail . Uten wraparound går køen tom for plass selv om det er ledige celler foran den.

Død celle

en celle som fortsatt inneholder en gammel verdi, men som ligger utenfor intervallet fra head til tail . Oppstår fordi Dequeue bare flytter head og aldri sletter. Døde celler skal med i svaret på en kø-håndkjøring — svarformatet er hele tabellen.

Amortisert kjøretid

O(1)

`Table-Insert`

\Theta(n)

Aggregert analyse

n

Doblingsstrategien

c > 1

Disjunkte mengder

en samling mengder uten felles elementer, der hver mengde har en representant. Operasjonene er Make-Set, Find-Set og Union . To elementer ligger i samme mengde nøyaktig når Find-Set gir samme representant for begge.

`Make-Set`

\Theta(1)

`Find-Set`

O(\lg n)

`Union` og `Link`

O(\lg n)

Rang

O(\lg n)

Skogrepresentasjon

hver disjunkt mengde lagres som et tre av forelderpekere, der rota peker på seg selv. Det finnes ingen ordning mellom nodene — pekerne betyr bare «tilhører samme mengde». Ikke forveksle med binære søketrær. Antall barn er ubegrenset, og nøkkelverdiene spiller ingen rolle.

Sjanger C — håndkjøring

oppgavetypen der du utfører operasjonene steg for steg og oppgir sluttilstanden. For en kø er svarformen hele tabellen inkludert døde celler, pluss head og tail . For Union-Find er den hvilke mengder som finnes og hvem som er representant. Delvis riktig gir delvis uttelling — skriv ned tilstanden underveis.

Sjanger D — definisjon med egne ord

oppgavetypen der du forklarer et begrep presist og kort. Svarformen er én til to setninger med hovedpoenget først. «Hva betyr amortisert kjøretid?» er den typiske definisjonsoppgaven fra dette kapitlet.

Repetisjonsoppgaver

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.

Innsetting nr.	Kapasitet etterpå	Kostnad	Sum så langt
1	1	1	1
2	2	2	3
3	4	3	6
4	4	1	7
5	8	5	12
6	8	1	13
7	8	1	14
8	8	1	15
9	16	9	24
10	16	1	25
11	16	1	26
12	16	1	27
13	16	1	28
14	16	1	29
15	16	1	30
16	16	1	31

Innsetting nr.	Kapasitet etterpå	Kostnad	Sum så langt
1	1	1	1
2	2	2	3
3	4	3	6
4	4	1	7
5	8	5	12
6	8	1	13
7	8	1	14
8	8	1	15
9	16	9	24
10	16	1	25
11	16	1	26
12	16	1	27
13	16	1	28
14	16	1	29
15	16	1	30
16	16	1	31