7.2 Drøft to strategier

Sjangeren «sammenlign to fremgangsmåter» — kjøretid (verste + forventet) og minne, med definert `n` og en klar konklusjon om når hver lønner seg.

45 min

6 oppgaver

Drøft to strategier

Din fremgang i kapitlet

0 / 6 oppgaver

Kapitlets plass i kurset

Bygger på

3.2Load-faktor, rehashing og hashmap/-set som verktøy

Drøftingsoppgaven er med i 4 av 7 sett (57 %), og andelen er økende —
alle fire forekomstene ligger i settene fra 2020 til 2023. Sjangeren er

- Sjanger K — drøft to strategier, altså at du får utlevert to
fremgangsmåter for det samme problemet og skal sammenligne dem på kjøretid
og minnebruk, og deretter si når hver av dem lønner seg.

Ett av de fire settene er høsten 2020, som var korona-hjemmeeksamen med alle
hjelpemidler. Den formen speiler ikke dagens eksamen, men oppgavetypen gjør det —
den kom igjen i tre ordinære sett etterpå.

Dette er den ene Del 2-oppgaven der du skriver prosa i stedet for pseudokode.
Sensorveiledningene omtaler den som oppgaven der sensor må bruke mest skjønn, og
det betyr to ting for deg: en velskrevet, presis tekst gir full uttelling, og en
tekst uten $O$ -notasjon gir nesten ingenting. Friheten gjelder formen, ikke
innholdet.

Prioritet: kunne (nivå 2 av tre — «må sitte» er nivå 1, «kjenne til» er
nivå 3). Sjangeren er lett å undervurdere fordi den ser ut som en gratis
skriveoppgave. Den er det motsatte: det er her de fleste taper poeng på noe så
enkelt som å ikke si hva $n$ betyr.

Slik er kapitlet lagt opp (45 min): tre løkker med teori, gjennomkjørt
eksempel og oppgaver. C er en god og vanlig karakter, og en drøfting som treffer
alle fire leddene under, er godt over det nivået.

Forkunnskaper

Dette kapitlet sammenligner strukturer du allerede kjenner — det lærer deg ingen
ny algoritme, bare hvordan du skriver om dem.

- kap. 1.1 — $O$ -notasjonen og vekstordningen. Hele
drøftingen føres i dette språket.
- kap. 3.2 — hashmap og hash-set, og hvorfor ordet
«forventet» aldri kan sløyfes. Har du brukt en ordbok i et program, er det
denne strukturen: Ordbøker.
- kap. 2.3 — counting sort og tellearrayet, og
forutsetningen om et kjent, begrenset verdiområde.
- kap. 7.1 — trie og hashmap, som er ett av de faste
sammenligningsparene.

Fra kap. 1.2 trengs løkketellingen, som er måten du
faktisk kommer fram til kjøretidene du skal sammenligne.

Notasjons- og pseudokodeliste

Løkke 1 — hva sensor faktisk ber om (ca. 8 min)

En bomstasjon skal vite om et kjøretøy har passert før i dag. To måter å gjøre
det på:

Den ene er å føre en liste over registreringsnumrene som har passert, og slå
opp i den ved hver passering. Den andre er å ha en tavle med én lampe for
hvert mulige registreringsnummer, og tenne lampen når bilen kjører forbi.

Begge virker. Den første bruker plass bare på de bilene som faktisk har kommet;
den andre bruker plass på alle biler som kunne kommet, men svarer til gjengjeld
uten å lete. Det er hele drøftingssjangeren i ett bilde: tid mot minne, og
hvilken av dem som er knapp i akkurat denne situasjonen.

Eksamensoppgaven kommer i én av to former. Enten får du to strategier utlevert og
skal sammenligne dem, eller så får du ett problem og skal foreslå to og velge.
Ordlyden er nesten alltid en variant av: «Sammenlign de to fremgangsmåtene på
kjøretid og minnebruk. Når lønner hver av dem seg?»

Drøftingsoppgaven (sjanger K)

O

📜Løsningsoppskrift: de fire leddene i en drøfting

Fire ledd, i denne rekkefølgen. De er sensors faktiske krav, og mangler ett av
dem, trekkes det.

1. Definér $n$ — og alle andre bokstaver du bruker. «La $n$ være antall
skanninger i loggen, $u$ antall forskjellige varenummer blant dem, og $k$
antall mulige varenummer.» Dette er ett eneste kort avsnitt, og det er det
billigste poenget i hele sjangeren.
2. Oppgi for hver strategi: verste kjøretid, forventet kjøretid og
minnebruk. Alle tre. Å oppgi bare forventet er halvt svar, og forventet uten
ordet «forventet» er feil svar.
3. Nevn kanttilfellene. Hva skjer når $k$ er enormt? Når alle nøklene
kolliderer? Når inndata allerede er ordnet? Det er i kanttilfellene de to
strategiene skiller lag, og det er derfor de er verdt poeng.
4. Konkludér. Én til tre setninger som sier hvilken strategi du velger, og
under hvilken betingelse den andre overtar.

Om ledd 4, som er det som skiller besvarelsene: en drøfting som ender i «det
kommer an på», har stanset ett skritt for tidlig. Sensor vet at det kommer an på
— spørsmålet er på hva. Skriv betingelsen: «Velg tellearrayet når $k$ er i
samme størrelsesorden som $n$ eller mindre; over det er hash-settet raskere og
bruker mindre minne.» Det er en konklusjon.

📝Oppgave 1

(Innstegsoppgave, sjanger K — drøft to strategier, altså at du sammenligner to
fremgangsmåter på kjøretid og minne og konkluderer.) For hver oppgavetekst: si
hva $n$ er, og hvilke andre størrelser som må navngis.

a) «Du skal telle hvor mange forskjellige varenummer som forekommer i en
lagerlogg.»
b) «Du skal finne alle ord i en ordliste som begynner med et gitt prefiks.»
c) «Du skal sjekke om to av tallene i et array summerer til $S$ .»

Løkke 2 — hash-set mot tellearray (ca. 16 min)

Dette er det vanligste paret i sjangeren, og det er verdt å kunne kaldt.

Et lagersystem logger hver skanning av et varenummer. Du skal finne ut hvor
mange forskjellige varenummer som forekommer i loggen. To strategier:

Strategi 1 — hash-set. Gå gjennom loggen én gang og legg hvert varenummer i
et hash-set. Settet ignorerer duplikater, så antall unike er størrelsen på settet
til slutt.

Strategi 2 — tellearray. Lag et array med én plass per mulige varenummer,
sett alle til usant, gå gjennom loggen og sett plassen til sant. Tell til slutt
hvor mange plasser som er sanne.

Begge er korrekte. Forskjellen ligger i hva de koster, og den forskjellen kan gå
begge veier.

Hash-set-profilen

O(n)

Tellearray-profilen

O(n + k)

✏️Eksempel 1: Full drøfting av lagerloggen

Et lagersystem har en logg med 200 000 skanninger. Varenumrene er heltall fra 0
til 999 999, og 3 500 forskjellige varer forekommer i loggen.

Sammenlign hash-set og tellearray på kjøretid (verste og forventet) og minne, og
konkludér. Sammenlign deretter med et system der «varenumrene» i stedet er
sensorkoder fra 0 til 255.

Ledd 1 — definisjoner. La

n

være antall skanninger i loggen,

u

antall
forskjellige varenummer som forekommer, og

k

størrelsen på verdiområdet, altså
hvor mange varenummer som er mulige. I det første tilfellet er

n = 200\,000

u = 3\,500

k = 1\,000\,000

Ledd 2 — kjøretid og minne.

Hash-set	Tellearray
Forventet tid	$O(n)$	$O(n + k)$
Verste tid	$O(n^2)$	$O(n + k)$ — samme, garantert
Minne	$O(u)$	$O(k)$
Grunnoperasjoner her	200 000	1 200 000
Minneceller her	3 500 oppføringer	1 000 000 plasser

Tallene i de to nederste radene er de to uttrykkene regnet ut for

n = 200\,000

u = 3\,500

k = 1\,000\,000

: tellearrayet gjør seks ganger så mange
grunnoperasjoner, og trenger rundt 286 ganger så mange lagringsplasser.
Ledd 3 — kanttilfeller.
- Stort verdiområde. Her er

k

fem ganger så stort som

n

. Da dominerer

k

-leddet, og tellearrayet betaler for en million varenummer for å telle

3 500.
- Alt kolliderer. Hash-settets $O(n^2)$ inntreffer bare hvis hashfunksjonen
er dårlig tilpasset dataene. Med tallnøkler og en fornuftig funksjon er det en

teoretisk mulighet, ikke en praktisk.

- Ukjent verdiområde. Vet du ikke $k$ på forhånd, er tellearrayet ikke
bare tregt — det er umulig. Hash-settet trenger ingen slik forutsetning.
Ledd 4 — konklusjon. Velg hash-settet her. Det er seks ganger raskere og
trenger under en halv prosent så mange lagringsplasser, og den eneste ulempen — $O(n^2)$ i verste
tilfelle — forutsetter en kollisjonskatastrofe som ikke inntreffer med
heltallsnøkler.
Det andre tilfellet snur konklusjonen. Med sensorkoder fra 0 til 255 er
$k = 256$ og $u = 240$ :

Hash-set	Tellearray
Grunnoperasjoner	200 000	200 256
Minneceller	240 oppføringer	256 plasser

Nå er de to praktisk talt like på papiret — men tellearrayet gjør ett
arrayoppslag der hash-settet gjør en hashberegning og en kollisjonssjekk, og det
har ingen

O(n^2)

i verste tilfelle. Velg tellearrayet når $k$ er i samme

størrelsesorden som $n$ eller mindre.
Terskelen, sagt i én setning: sammenlign $k$ med $n$ . Er $k$ vesentlig større

enn $n$ , vinner hash-settet; er $k$ mindre enn eller omtrent lik $n$ , vinner
tellearrayet, og da med garanterte kjøretider i tillegg.
Poengtrapp-notat. Hovedmomentet er terskelen: at valget avhenger av $k$ mot
$n$ , ikke av hvilken struktur som er «finest». Den innsikten alene gir mest.

Deretter kommer de tre kjøretidene, minnebruken, og til slutt kanttilfellene. En
besvarelse som bare sier «hash-set er $O(1)$ , altså raskest», har hoppet over
både ordet «forventet» og hele $k$ -aksen, og lander lavt.

📝Oppgave 2

Sjanger K

En nettbutikk vil vite hvor mange forskjellige kunder som har
handlet i løpet av et døgn. Loggen har 4 000 000 ordrelinjer. Kunde-id er et
heltall fra 0 til 50 000 000 (alle kunder som noen gang er registrert), og rundt
120 000 forskjellige kunder handlet dette døgnet.

Sammenlign hash-set og tellearray etter de fire leddene, og konkludér.

✏️Eksempel 2: En midtnivåbesvarelse på samme oppgave — hva som mangler

Under står en besvarelse på oppgave 2 som ligger rundt karakteren B. Den er
korrekt, og den ville fått uttelling. Les den, og finn ut hva som skiller den fra
besvarelsen i eksempel 1.

«Hash-settet er raskest, med $O(1)$ per innlegg og $O(n)$ totalt.
Tellearrayet må sette av plass til alle mulige kunde-id-er, som er veldig mange
her, så det bruker mye mer minne. Jeg velger hash-settet.»

Hva som er bra nok: besvarelsen velger riktig strategi, den refererer til

O

-notasjon, og den peker på minnet som den avgjørende forskjellen. Det er
hovedmomentet, og hovedmomentet gir mest. Dette er en ekte B — ikke en
nødløsning.

Hva som mangler til A, punkt for punkt:

- $n$ er ikke definert. « $O(n)$ totalt» — $n$ er hva? Ordrelinjer eller
kunder? Dette er felle #10, og det er det eneste punktet i hele sjangeren
som er dokumentert med et eksplisitt trekk i arkivet.
- Ordet «forventet» mangler. « $O(1)$ per innlegg» er feil slik det står.
Hash-settet er $O(1)$ forventet; verste tilfelle er $O(n)$ per innlegg.
- Verste tilfelle er ikke nevnt for noen av strategiene. Oppgaven ber om
begge, og tellearrayets garanterte $O(n + k)$ er faktisk et argument i
tellearrayets favør som besvarelsen taper ved å hoppe over det.
- «Veldig mange» er ikke et tall. $k$ er over 50 millioner mot $n$ på 4
millioner. Å skrive forholdet ut er det som gjør konklusjonen etterprøvbar.
- Konklusjonen mangler betingelsen. «Jeg velger hash-settet» er et valg, ikke
en konklusjon. Den blir en konklusjon når du legger til når det motsatte ville
gjeldt: «…men hadde id-ene ligget tett i et lite område, ville tellearrayet
vært bedre, fordi $k$ -leddet da forsvinner.»

Merk hva som IKKE er feil i besvarelsen. Den er kortfattet, den bruker
hverdagsspråk, og den skriver ingen pseudokode. Alt det er helt greit i denne
sjangeren. Det som trekker, er de fem manglene over, og fire av dem koster deg
under ett minutt å rette opp.

Typiske feil

- Å bruke $n$ uten å definere det. Felle #10, og den dyreste i denne
sjangeren fordi den rammer hele besvarelsen: har du ikke sagt hva $n$ er, kan
sensor ikke etterprøve en eneste kjøretid du oppgir. Skriv definisjonene som
første avsnitt, alltid.
- Å ikke referere til $O$ -notasjon i det hele tatt. En tekst som sier at «den
ene er raskere når det er mye data», svarer ikke på oppgaven. Sjangeren er
åpen i formen, ikke i innholdet.
- Å oppgi bare forventet kjøretid — eller bare verste. For hash-baserte
strukturer er begge en del av svaret, og forskjellen mellom dem ( $O(n)$ mot
$O(n^2)$ ) er ofte selve poenget i kanttilfelle-avsnittet.
- Å sløyfe ordet «forventet». «Hashmap er $O(1)$ » er ikke en forkortelse, det
er en feil påstand.
- Å glemme minneaksen. Oppgaven ber om kjøretid og minne. To strategier
med samme kjøretid kan skille lag fullstendig på minne — det er nettopp
tellearrayets situasjon.
- Å stanse ved «det kommer an på». Uten betingelsen er det ikke en
konklusjon. Skriv terskelen: «når $k$ er større enn $n$ …».
- Å blande $n$ , $u$ og $k$ . Tre forskjellige tall, tre forskjellige
bokstaver. Denne feilen ser liten ut og gjør hele regnestykket uleselig.

Løkke 3 — en ukjent sortering mot en du kan (ca. 14 min)

— naturlig pausepunkt —

Den andre faste varianten er at du får utlevert pseudokode du aldri har sett,
og skal sammenligne den med en sortering fra pensum. Poenget er ikke om du
kjenner navnet. Poenget er om du kan lese hva algoritmen flytter, telle løkkene,
og plassere den.

Framgangsmåten fra kap. 2.3 gjelder: se på hva som flyttes
og hvor langt. Bare nabobytter gir stabilitet; ingen ekstra array gir in-place;
en peker som kan gå bakover gjør at antall gjennomløp avhenger av hvor uordnet
inndata er.

Her sammenligner vi gnome sort — én peker som går fram når naboparet står
riktig, og bytter og går ett steg tilbake når det står feil — med
flettesortering, som deler i to, sorterer hver halvdel og fletter.

Verste, forventet og beste kjøretid

O(n^2)

✏️Eksempel 3: Eksamensnivå — gnome sort mot flettesortering

Et system mottar 8 målinger av gangen og skal sortere dem. Sammenlign gnome sort
og flettesortering på kjøretid (verste, beste og forventet), minne og stabilitet.
Konkludér.

Måledataene kommer fra en sensor som leverer nesten sortert: hver ny måling er
som regel litt større enn den forrige, men to og to bytter av og til plass.

Ledd 1 — definisjoner. La

n

være antall målinger som sorteres av gangen,
her

n = 8

. Alle kjøretider under er målt i antall sammenligninger og bytter,
som er de to operasjonene begge algoritmene bruker.

Ledd 2 — kjøretid, minne og stabilitet.

Gnome sort	Flettesortering
Verste tid	$O(n^2)$	$O(n \log n)$
Beste tid	$O(n)$	$O(n \log n)$
Forventet tid	$O(n^2)$	$O(n \log n)$
Minne	$O(1)$ — in-place	$O(n)$ — trenger et hjelpearray
Stabil	ja	ja

De fire radene øverst er telt på fire konkrete inndata med

n = 8

Inndata (8 tall)	Gnome: sammenligninger	Gnome: bytter	Flettesortering: sammenligninger
allerede sortert	7	0	12
nesten sortert (ett par byttet om)	9	1	12
tilfeldig	33	14	17
motsatt sortert	56	28	12

Les den tabellen én gang til. På allerede sortert og nesten sortert input
gjør gnome sort færre sammenligninger enn flettesortering. På motsatt sortert
input gjør den nesten fem ganger så mange.
Ledd 3 — kanttilfeller. Gnome sorts antall bytter er nøyaktig antall par som

står i feil rekkefølge. På motsatt sortert input er det $n(n-1)/2$ , altså 28 for

$n = 8$ og 2 016 for $n = 64$ — kvadratisk vekst, målt og ikke gjettet. På
allerede sortert input er det 0 bytter og $n - 1$ sammenligninger, altså rent
lineært. Flettesortering gjør omtrent like mye arbeid uansett; det er både dens
styrke og dens svakhet.
Ledd 4 — konklusjon, og den er ikke den opplagte. For dette systemet
velger jeg gnome sort. To grunner, som begge følger av oppgaveteksten:

inndata er beskrevet som nesten sortert, og det er nøyaktig gnome sorts beste
tilfelle, der den er $O(n)$ mot flettesorteringens $O(n \log n)$ . Og $n = 8$ er
lite og fast, så den asymptotiske forskjellen får aldri virke — men

flettesorteringens hjelpearray koster minne i hver eneste runde.
Men konklusjonen snur straks forutsetningen gjør det. Kan dataene komme i
vilkårlig rekkefølge, eller kan $n$ vokse, er flettesortering det riktige valget:
$O(n \log n)$ garantert slår $O(n^2)$ forventet, og forskjellen blir grov fort.
Gnome sort er valgbar her bare fordi oppgaveteksten sier både «8 målinger» og
«nesten sortert».

Poengtrapp-notat. Det som gir mest, er å knytte valget til en navngitt
forutsetning i oppgaveteksten. En besvarelse som velger flettesortering fordi
$O(n \log n)$ er bedre enn $O(n^2)$ , er ikke feil — den er korrekt og får god
uttelling — men den har oversett at oppgaven har fortalt deg noe om inndata, og
det er akkurat den lesningen sensorveiledningene etterspør når de gjentar «les
oppgaveteksten svært nøye».

📝Oppgave 3

Sjanger K

Et søkefelt i en app skal foreslå ord mens brukeren skriver.
Ordlista har 300 000 ord, og det lengste er 24 bokstaver. Sammenlign et trie
og et hashmap på kjøretid og minne for de to operasjonene SettInn(ord) og
Forslag(prefiks), og konkludér.

📝Oppgave 4

Sjanger K

Et program skal avgjøre om to av tallene i et array summerer til et
gitt tall $S$ . Sammenlign:

a) Sortér arrayet, og gå deretter gjennom det med to pekere, én fra hver
ende.
b) Gå gjennom arrayet én gang, og slå opp i et hash-set om komplementet
$S - x$ er sett før.

Oppgi kjøretid (verste og forventet) og minne for hver, og konkludér.

📝Oppgave 5

Sjanger K, eksamensnivå

En graf over 40 000 nettsider og lenkene mellom dem
skal lagres. Sammenlign naboliste og nabomatrise på minnebruk og på
kjøretiden for de to operasjonene «finnes det en lenke fra $u$ til $v$ ?» og «list
alle lenker ut fra $u$ ».

Konkludér for to tilfeller: et nettsted der hver side lenker til rundt 20 andre,
og et lite, tett nettverk der nesten alle sider lenker til nesten alle.

Oppgaveteksten inneholder nesten alltid den forutsetningen som avgjør svaret.
Disse fem er verdt å lese etter, og de dukket opp i oppgavene over:

- «heltall fra 0 til …» eller «et fast, kjent område» — verdiområdet $k$
er oppgitt. Sammenlign $k$ med $n$ ; er $k$ lite, er tellearray eller counting
sort i spill.
- «nesten sortert» eller «kommer i tilnærmet rekkefølge» — beste tilfelle
er relevant, og en $O(n^2)$ -sortering kan slå en $O(n \log n)$ -sortering.
- «prefiks», «begynner med» eller «mens brukeren skriver» — trie mot
hashmap.
- «minnet er knapt» eller «kjører på en liten enhet» — minneaksen veier
tyngst, og in-place-egenskapen blir et argument.
- «hver side lenker til rundt …» — grafen er glissen, og nabolister vinner.

Står ingen slik forutsetning i teksten, må du selv si hvilken du antar:
«Jeg antar at verdiområdet ikke er kjent på forhånd.» Da er drøftingen fortsatt
etterprøvbar, og sensor kan følge resonnementet ditt.

📝Oppgave 6

Sjanger K

Les denne besvarelsen på en drøftingsoppgave om å finne duplikater
i et array, og pek ut nøyaktig hva som mangler.

«Med et hash-set går det i $O(1)$ , mens sortering går i $O(n \log n)$ .
Hash-settet er derfor best. Sortering bruker mindre minne.»

a) Hvilke av de fire leddene i oppskriften er dekket?
b) Skriv om besvarelsen så den treffer alle fire.

Begrepsbank

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

De fire leddene i en drøfting

n

Å definere

n

— og de andre bokstavene

n

Valget mellom hash-set og tellearray

k

Minnebruk som egen akse

O(k)

Kanttilfellene som gir delpoeng

k

Konklusjonskravet

k

Beste tilfelle som drøftingsargument

O(n)

Signalordene i oppgaveteksten

k

Hvorfor prosa kan gi full uttelling

O

Poengtrappen i en drøfting

k

Repetisjon — kapitlet på ett kort

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 Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.