Indholdsfortegnelse

Svarark — Post 2 (facit)
#

Øvelse 1 — Opslag på index
#

Hvor mange personer skulle programmøren spørge for at finde ordet?

Svar: 1

Hvad er kompleksiteten? O(1)

Ville det gøre en forskel hvis I var 1.000 personer i rækken?

Nej — du går direkte til den rigtige plads via index. Antallet af personer er ligegyldigt.

Hvilken strategi brugte programmøren?

Spørger fra index 0 og frem — én ad gangen.

Hvor mange personer skulle programmøren spørge for at finde ordet?

Svar: varierer — afhænger af hvor i rækken elementet ligger.

Hvad er kompleksiteten? O(n)

Ville det gøre en forskel hvis I var 1.000 personer i rækken? Eller hvis ordet ikke fandtes i rækken?

Ja — jo flere personer, jo flere skal spørges. Hvis ordet ikke findes skal alle spørges. Worst case er O(n).

Hvor mange personer blev påvirket da programmøren stillede sig i rækken?

Svar: alle til højre for indsætningspunktet — de opdaterede alle deres tal.

Hvad er kompleksiteten? O(n)

Ville det gøre en forskel hvis I var 1.000 personer i rækken?

Ja — jo flere personer til højre, jo flere skal opdatere deres tal. Worst case er alle.

Ville det gøre en forskel hvis programmøren havde stillet sig på den sidste plads i rækken? Hvilken kompleksitet ville det give?

Ingen skulle opdatere deres tal — indsættelse sidst er O(1). Det er derfor ArrayList er effektiv til at tilføje elementer til sidst.

Hvor mange personer blev påvirket da personen forlod pladsen?

Svar: alle til højre for den slettede — de opdaterede alle deres tal.

Hvad er kompleksiteten? O(n)

Ville det gøre en forskel hvis I var 1.000 personer i rækken?

Ja — jo flere personer til højre, jo flere skal opdatere deres tal.

Ville det gøre en forskel hvis personen der forlod pladsen havde stået på den sidste plads i rækken? Hvilken kompleksitet ville det give?

Ingen skulle opdatere — sletning sidst er O(1).