6.3 Algoritmedefinisjon, pseudokode og kompleksitet (Big-O)

Hva en algoritme er, pseudokode, og kjøretidskompleksitet/Big-O — teoristoffet om binærsøk vs. sekvensielt søk og «brute force».

45 min

7 oppgaver

Algoritmedefinisjonpseudokodekompleksitet (Big-O)

Din fremgang i kapitlet

0 / 7 oppgaver

Kapitlets plass i kurset

Bygger på

6.2Søking: sekvensielt søk og binærsøk

Brukes videre i

6.PPrøver til del 6: Algoritmer — binærsøk, sortering og kompleksitet

Algoritmeteori er belagt i 4 av de 10 eksamenssittingene i arkivet (2014–2019) — omtrent 40 %, og tyngst i settene fra 2016 og 2017.

Det kommer alltid som sjanger A — teori/flervalg, altså spørsmål med fire alternativer der ett er riktig. Slike spørsmål er samlet i Oppgave 1, som er ~25 % av hele settet, og algoritmespørsmålene utgjør et par av de rundt tjue. Typiske formuleringer: «Hvilken kjøretidskompleksitet har binærsøk?», «Hva forutsetter binærsøk?», «Hva menes med brute force?».

Prioritet: dette bør du kjenne til — nivå 3, det laveste av bokas tre nivåer «må sitte», «må kunne» og «bør kjenne til».

Og her er den ærlige avveiningen: stoffet er billig, ikke viktig. Det tar 45 minutter å lære, det kan ikke løses ved å tenke seg om i eksamenslokalet, og det er verdt et par flervalgspoeng. Det er en god handel — men det er også alt. Er du usikker på programmeringskjeden i Del 7, som alene er 50–60 % av settet, skal du dit først.

Et siste poeng verdt et minutt: det finnes ingen minuspoeng på flervalg i dette emnet fra 2015. Blankt teller nøyaktig like mye som feil, altså null, så kryss alltid av — også når du bare gjetter.

Forkunnskaper

- kap. 6.2 — sekvensielt søk og binærsøk. Hele kompleksitetsdelen sammenligner nettopp de to.
- kap. 6.1 — boblesortering, som er kapitlets tredje eksempel.

Kapitlet krever ingen ny Python. Det er rent teoristoff, og du kan lese det uten å skrive en eneste linje kode.

To mykere innganger til det samme: Algoritmer og pseudokode forklarer algoritmebegrepet fra bunnen, og Rekursjon og algoritmekompleksitet tar kompleksitet på videregående-nivå.

Har du aldri hatt informatikk: en algoritme er ganske enkelt en oppskrift på hvordan et problem løses, og det er den vi nå skal gi et presist innhold.

Løkke 1 — hva er egentlig en algoritme? (~10 min)

Tenk på framgangsmåten for å bytte en punktert sykkelslange. «Fiks dekket» er ikke en framgangsmåte — det er en ønskeliste. «Løsne begge bremseklossene, skru av hjulmutrene, ta av hjulet, lirk dekket av felgen på den ene siden …» er en framgangsmåte: hvert steg er utvetydig, og det er et bestemt antall av dem.

Den forskjellen er nøyaktig forskjellen mellom en løs beskrivelse og en algoritme. Eksamensspørsmålene om algoritmebegrepet handler alltid om et av de tre kravene under, så det lønner seg å kunne dem som en liste.

Algoritme

En entydig og endelig oppskrift som løser et bestemt problem: en ordnet rekke steg som tar en gitt inndata og gir en bestemt utdata. De tre kravene er alle nødvendige. Er stegene tvetydige, kan to personer få ulikt svar. Er de uendelig mange, blir du aldri ferdig. Og løser oppskriften ikke et bestemt problem, er den ikke en algoritme, men bare en liste med instruksjoner. En algoritme er uavhengig av programmeringsspråk — den samme algoritmen kan skrives i Python, på papir eller i pseudokode.

Entydighet

Hvert steg i en algoritme har nøyaktig én mulig tolkning. «Legg til litt salt» er ikke entydig; «legg til 5 gram salt» er det. I kode er entydigheten gratis — maskinen kan ikke gjette — men i pseudokode og i en muntlig beskrivelse må du passe på den selv. Dette er kravet flervalgsoppgaver oftest tester, ved å tilby et alternativ som er en vag beskrivelse i stedet for en oppskrift.

Endelighet (terminering)

En algoritme må stoppe etter et endelig antall steg, uansett hvilken lovlig inndata den får. Dette er ikke en formalitet: en while -løkke med feil oppdatering av grensene — som binærsøket uten + 1 i kap. 6.2 — bryter kravet og henger for alltid. Merk at antall steg gjerne avhenger av inndataene; kravet er bare at det er endelig for hver enkelt inndata.

Inndata og utdata

En algoritme tar imot null eller flere inndata og gir én eller flere utdata . Sammenhengen mellom dem er problemet algoritmen løser. For binærsøk er inndataene ei sortert liste og en verdi, og utdataen er en indeks eller -1 . Å kunne beskrive en algoritme ved inndata og utdata — uten å nevne en eneste kodelinje — er nettopp det sjanger C spør etter: «forklar med én setning hva funksjonen gjør».

✏️Eksempel 1: et gjennomgått flervalg om algoritmebegrepet

Hvilken av disse beskrivelsene er en algoritme?

a) «Finn den billigste leverandøren i lista.»
b) «Sett beste til første rad. Gå gjennom de øvrige radene én for én, og erstatt beste hver gang du finner en rad med lavere pris. Returner beste til slutt.»
c) «Bruk en effektiv metode for å gå gjennom lista til du er fornøyd med resultatet.»
d) «Lista skal sorteres slik at den billigste leverandøren kommer først.»

Riktig svar: b)

Bare b) oppfyller alle tre kravene: hvert steg er entydig, antallet steg er endelig (én runde per rad), og oppskriften løser et bestemt problem.

Slik faller de tre andre:

- a) er en problembeskrivelse, ikke en løsning. Den sier hva som skal oppnås, ikke hvordan. Dette er den nære distraktoren som fanger flest, fordi setningen er helt presis — den er bare presis om feil ting.
- c) bryter entydigheten to ganger: «en effektiv metode» sier ikke hvilken, og «til du er fornøyd» er ikke et stoppkriterium en maskin kan sjekke.
- d) beskriver et ønsket resultat, altså en tilstand etterpå. Det er heller ikke steg.

Legg merke til hva som ikke avgjorde: ingen av alternativene måtte være skrevet i Python. En algoritme er språkuavhengig, og b) er skrevet på norsk.

📝Oppgave 1

(Innstegsoppgave, sjanger A — teori/flervalg, altså et spørsmål med fire alternativer der ett er riktig.) Hvilket av kravene til en algoritme brytes av oppskriften «Trekk fra 1 så lenge tallet er positivt, og skriv ut resultatet» når den kjøres på tallet $-5$ ?

a) Entydigheten — «positivt» kan tolkes på flere måter
b) Kravet om inndata — oppskriften mangler et startpunkt
c) Endeligheten — oppskriften stopper aldri på dette tallet
d) Ingen av dem — oppskriften er en gyldig algoritme

Løkke 2 — pseudokode (~8 min)

Når du skal beskrive en algoritme for et menneske, er Python både for detaljert og for spesifikt: kolon, innrykk og len() er Python-vaner, ikke deler av ideen. Pseudokode er mellomformen — kode-lignende steg skrevet i klarspråk, uten et bestemt språks regler.

Du møter pseudokode i to sammenhenger på eksamen: i teorispørsmål om hva pseudokode er, og av og til som formen en algoritme presenteres i før du skal oversette den til Python.

Pseudokode

En beskrivelse av en algoritme i en form som ligner kode, men som er skrevet for mennesker og ikke følger noe programmeringsspråks syntaks. Den skal ikke kunne kjøres, og den trenger verken riktige kolon, importer eller variabeldeklarasjoner. Til gjengjeld må den fortsatt være entydig: hvert steg skal kunne oversettes til kode på nøyaktig én måte. Pseudokode brukes for å planlegge en løsning, for å sammenligne algoritmer, og for å beskrive dem i en lærebok uten å binde seg til ett språk.

✏️Eksempel 2: fra pseudokode til Python

Under står sekvensielt søk i pseudokode. Oversett den til Python, og pek på hva som er lagt til i oversettelsen.

Pseudokoden — legg merke til at den ikke er kjørbar, og ikke prøver å være det:

søk(liste, mål):
    for hver plass i lista, fra første til siste:
        hvis elementet på denne plassen er lik mål:
            gi tilbake plassnummeret, og stopp
    gi tilbake -1

Oversettelsen:

def sok(liste, mal):
    for i in range(len(liste)):
        if liste[i] == mal:
            return i
    return -1

print(sok([14, 29, 8, 51], 8))
print(sok([14, 29, 8, 51], 30))

Utskrift:

2
-1

Hva ble lagt til? range(len(liste)) i stedet for «fra første til siste», kolon og innrykk i stedet for norske ord, og return i stedet for «gi tilbake». Ingen av delene endret algoritmen — de er Python-vaner.

Hva ble ikke lagt til? Ingenting. Det er testen på god pseudokode: oversettelsen skal ikke kreve at du tar en eneste ny beslutning.

Typiske feil: algoritmer og pseudokode

Fire misforståelser går igjen, og alle fire er testet som flervalg:

- «Pseudokode må kunne kjøres.» Nei — da hadde det vært kode. Kravet er at den er entydig, ikke at den er syntaktisk riktig.
- «En algoritme er det samme som et program.» Nei. Algoritmen er ideen; programmet er én bestemt nedskriving av den i ett bestemt språk. Den samme algoritmen kan skrives i Python og i pseudokode, og er den samme algoritmen begge steder.
- «Alt som er en oppskrift, er en algoritme.» Nei — den må også være entydig og endelig. «Rør til det ser bra ut» er en oppskrift, men ikke en algoritme.
- «En algoritme må ha inndata.» Ikke nødvendigvis; kravet er null eller flere. En algoritme som skriver ut de hundre første primtallene, tar ingen inndata.

📝Oppgave 2

Sjanger C

Under står en algoritme i pseudokode.

ukjent(tabell):
    sett teller til 0
    for hver rad i tabellen:
        hvis raden har flere enn 3 felt:
            øk teller med 1
    gi tilbake teller

a) Skriv én presis setning om hva algoritmen gir tilbake.
b) Oversett pseudokoden til Python.

Løkke 3 — kjøretidskompleksitet (~17 min)

Du har to funksjoner som gjør den samme jobben, og begge kjører på et blunk når du tester dem på ti elementer. Hvilken skal du velge?

Spørsmålet gir ikke mening før du spør videre: hva skjer når lista blir stor? Det er hele poenget med kjøretidskompleksitet. Vi teller ikke sekunder — de avhenger av maskinen, av språket og av hvor mye annet som kjører — vi ser på hvordan arbeidet vokser når mengden data vokser.

Ta binærsøk mot sekvensielt søk. På ti elementer er forskjellen usynlig. På en million er den forskjellen på 20 steg og en million.

— naturlig pausepunkt —

Input-størrelsen

n

n

Kjøretidskompleksitet

n

Verste tilfelle

n

Big-O-notasjon

O(\ldots)

O(1)

— konstant tid

O(1)

O(\log n)

— logaritmisk tid

n

O(n)

— lineær tid

O(n)

O(n^2)

— kvadratisk tid

\displaystyle \frac{n(n-1)}{2}

O(2^n)

— eksponentiell tid

Arbeidsmengden dobles hver gang du legger til ett element. Dette er klassen der problemene blir praktisk uløselige. Tallene illustrerer hvorfor: 20 elementer gir omtrent en million, 30 gir en milliard, 40 gir tusen milliarder. Algoritmer i denne klassen er brukbare bare på svært små inndata, og de dukker opp når en løsning må prøve alle kombinasjoner av valg.

O(n!)

— faktoriell tid

n

📜Slik kjenner du igjen klassen i din egen kode

Du skal ikke gjøre formell analyse i dette emnet. Du skal kunne kjenne igjen formen, og det gjøres ved å telle løkker:

1. Ingen løkke over dataene $\to$ $O(1)$ . Du henter én verdi, uansett hvor mye data det er.
2. Én løkke gjennom dataene $\to$ $O(n)$ . Dette er de aller fleste funksjonene du skriver i faget.
3. En løkke inne i en løkke, begge over dataene $\to$ $O(n^2)$ . Boblesortering, og «sammenlign hver rad med hver rad».
4. Halverer arbeidet i hvert steg $\to$ $O(\log n)$ . Binærsøk er det eneste eksemplet i pensum.
5. Prøver alle kombinasjoner eller alle rekkefølger $\to$ $O(2^n)$ eller $O(n!)$ . Brute force.

Merk et vanlig feilgrep i punkt 3: en løkke inne i en løkke er bare $O(n^2)$ hvis begge går over dataene. Går den indre løkka over de sju ukedagene, uansett hvor stor tabellen er, er den en konstant — og hele funksjonen er $O(n)$ .

✏️Eksempel 3: tallene bak klassene

Sett opp hvor mye arbeid de tre algoritmene fra Del 6 gjør for 10, 100, 1 000 og 1 000 000 elementer — og vurder hvilke av dem som er brukbare.

Tallene er antall grunnoperasjoner i verste tilfelle: halveringer for binærsøk, sammenligninger for de to andre.

Antall elementer $n$	Binærsøk $O(\log n)$	Sekvensielt søk $O(n)$	Boblesortering $O(n^2)$
10	4	10	45
100	7	100	4 950
1 000	10	1 000	499 500
1 000 000	20	1 000 000	499 999 500 000

Tre observasjoner er verdt å ta med seg:
- For 10 elementer er alle tre like gode. Forskjellene er usynlige, og det er derfor kompleksitet ikke er noe du merker når du tester på småeksempler.
- For 1 000 000 er forskjellen avgjørende. Binærsøket er ferdig på 20 steg. Boblesorteringen ville gjort omtrent 500 milliarder sammenligninger — det er ikke tregt, det er praktisk umulig.
- Kolonnen for boblesortering vokser fortest. Fra 1 000 til 1 000 000 elementer, altså tusen ganger mer data, går arbeidet opp en million ganger. Det er det

O(n^2)

betyr i praksis.
Regnestykket for boblesortering er

\displaystyle \frac{n(n-1)}{2}

: for

n = 100

gir det

\displaystyle \frac{100 \times 99}{2} = 4\,950

📝Oppgave 3

Eksamensnivå, sjanger A

Hvilken kjøretidskompleksitet har binærsøk i ei sortert liste med $n$ elementer?

a) $O(n^2)$
b) $O(n)$
c) $O(1)$
d) $O(\log n)$

📝Oppgave 4

Eksamensnivå, sjanger A

Boblesortering gjør $\displaystyle \frac{n(n-1)}{2}$ sammenligninger på ei liste med $n$ elementer.

a) Hvor mange sammenligninger blir det for 200 elementer?
b) Lista dobles fra 200 til 400 elementer. Hvor mange ganger flere sammenligninger blir det da, omtrent?
c) Hva heter vekstklassen dette er et eksempel på?

Løkke 4 — lønner det seg å sortere først? (~10 min)

Nå kan du sette de to kapitlene sammen. Binærsøk er dramatisk raskere enn sekvensielt søk — men det krever ei sortert liste, og sortering koster. Spørsmålet er når regnestykket går opp.

Svaret følger av tallene: å sortere 1 000 elementer med boblesortering koster nesten 500 000 sammenligninger, mens ett sekvensielt søk koster høyst 1 000. Skal du slå opp én gang, er sortering helt bortkastet. Skal du slå opp tusen ganger i den samme lista, betaler sorteringen seg fort inn, fordi hvert oppslag da koster 10 steg i stedet for 1 000.

Dette er den eneste avveiningen fra dette kapitlet du vil få bruk for i en programmeringsoppgave — og på eksamen ender du nesten alltid på sekvensielt søk, fordi tabellene er små og oppslagene få.

Brute force (uttømmende søk)

En løsningsmetode som prøver alle muligheter og velger den beste, i stedet for å bruke et smartere resonnement. Metoden har to egenskaper som alltid nevnes sammen: den finner garantert det riktige svaret, og den blir ubrukelig fort når problemet vokser, fordi antall muligheter typisk vokser eksponentielt eller faktorielt. Å prøve alle passord av en gitt lengde er brute force; det samme er å prøve alle ruter mellom byer.

Handelsreisendes problem

(n-1)!

✏️Eksempel 4: et gjennomgått flervalg om brute force

Hva kjennetegner en brute force-løsning?

a) Den finner en god løsning raskt, men uten garanti for at den er den beste.
b) Den halverer søkeområdet i hvert steg og krever sorterte data.
c) Den prøver alle mulighetene og finner garantert den beste, men blir fort uhåndterlig.
d) Den bruker mindre minne enn andre metoder, på bekostning av kjøretid.

Riktig svar: c)

Begge halvdelene av setningen må være med: garantien for riktig svar er den ene siden av brute force, og den eksplosive veksten er den andre. Et alternativ som bare nevner den ene, er ufullstendig.

Slik faller de tre andre:

- a) beskriver det motsatte — en heuristikk, altså en metode som gir en god nok løsning uten garanti. Dette er den nærmeste distraktoren, fordi det er nettopp slike metoder man bruker i stedet for brute force på store problemer.
- b) beskriver binærsøk. Halvering og sorteringskrav er binærsøkets kjennetegn, ikke brute force sitt.
- d) handler om minnebruk, som ikke er en del av definisjonen i det hele tatt.

Legg merke til teknikken som avgjorde: hvert av de fire alternativene er en korrekt beskrivelse av noe — bare ett av dem beskriver brute force. Det er slik teori-flervalgene i dette emnet er bygget, og derfor må du lese alle fire før du krysser av.

📝Oppgave 5

Eksamensnivå, sjanger A

Hvorfor krever binærsøk at lista er sortert?

a) Fordi «er midten for lite, er alt til venstre også for lite» bare holder i ei sortert liste
b) Fordi while-løkka ellers ikke ville stoppet, og programmet ville hengt seg opp for godt
c) Fordi imid ellers kunne blitt en indeks utenfor lista og gitt IndexError ved oppslag
d) Fordi indeksene ellers ikke ville stått i stigende rekkefølge i det gjenstående søkevinduet

📝Oppgave 6

Eksamensnivå, sjanger A

Et program skal slå opp postnumre i et register med 1 000 rader. Registeret leses fra fil i vilkårlig rekkefølge.

a) Hvor mange sammenligninger bruker ett sekvensielt søk i verste tilfelle?
b) Alternativet er å boblesortere registeret først og deretter binærsøke. Hvor mange sammenligninger koster sorteringen, og hvor mange koster hvert oppslag etterpå?
c) Programmet skal gjøre 5 oppslag. Hvilken framgangsmåte er billigst? Begrunn med tallene.
d) Hva om programmet skal gjøre 5 000 oppslag?

📝Oppgave 7

Eksamensnivå, sjanger A

En funksjon går gjennom alle radene i en tabell med $n$ rader, og for hver rad går den gjennom de tolv månedene i året og summerer. Hvilken kjøretidskompleksitet har funksjonen?

a) $O(n^2)$ , fordi den har en løkke inne i en løkke
b) $O(n)$ , fordi den indre løkka har et fast antall runder
c) $O(\log n)$ , fordi den behandler dataene i grupper
d) $O(1)$ , fordi antall måneder ikke avhenger av tabellen

Typiske feil: kompleksitet

Feilkode #11 i bokas register er «forveksle tett formulerte alternativer», og i akkurat dette stoffet har den fire faste former:

- Å bytte om $O(\log n)$ og $O(n)$ . Binærsøk er $O(\log n)$ , sekvensielt søk er $O(n)$ . Huskeregelen: det som halverer, er logaritmisk.
- Å tro at binærsøk virker på ei usortert liste. Den vanligste enkeltfeilen i hele Del 6, og den koster to poeng: ett på kompleksitetsspørsmålet og ett på forutsetningsspørsmålet.
- Å telle løkker uten å se hva de går over. En løkke inne i en løkke er bare $O(n^2)$ hvis begge går over dataene.
- Å blande brute force med en effektiv metode. Brute force prøver alle muligheter og er derfor treg, men den garanterer riktig svar. En rask metode som ikke garanterer det beste svaret, er det motsatte.

En femte, mildere felle: å oppgi en kompleksitet uten å si hva $n$ er, eller uten å si om det gjelder verste eller beste tilfelle. Sier oppgaven ingenting, mener den verste tilfelle.

Avgrensning — dette skal du IKKE kunne

Boka stopper her, og det er med vilje. Formell asymptotisk analyse er utenfor pensum i TDT4110: du skal ikke bevise at en algoritme er $O(n \log n)$ , ikke arbeide med $\Omega$ og $\Theta$ , og ikke utlede kompleksiteten til en algoritme du ikke har sett før. Det hører hjemme i senere algoritmeemner.

Det du skal kunne, er de fem klassene i dette kapitlet, hvilken algoritme som hører til hvilken, og hvorfor. Ser du et eksamensspørsmål som krever mer enn det, har du sannsynligvis lest det for komplisert.

Én ting til, som du bør kjenne til uten å pugge: Pythons innebygde sorted() og .sort() er langt raskere enn boblesortering — de er $O(n \log n)$ , ikke $O(n^2)$ . Det er en av grunnene til at fasitene bruker dem fritt.

Repetisjon — de seks setningene du bør ha med deg

Begreps- og enhetsliste

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.