Svarark — Post 3 (facit)#
Øvelse 1 — Opslag på index#
Hvor mange personer skulle I gå forbi for at finde den rigtige?
Svar: varierer — du skal tælle dig frem fra første person.
Hvad er kompleksiteten? O(n)
Ville det gøre en forskel hvis I var 1.000 personer i kæden?
Ja — du skal tælle dig frem fra starten hver gang. Jo flere personer, jo længere tid.
Øvelse 2 — Find specifikt element#
Hvilken strategi brugte programmøren?
Spørger fra første person i kæden og frem — én ad gangen.
Hvor mange personer skulle programmøren spørge for at finde ordet?
Svar: varierer — afhænger af hvor i kæden elementet ligger.
Hvad er kompleksiteten? O(n)
Ville det gøre en forskel hvis I var 1.000 personer i kæden? Eller hvis ordet ikke fandtes?
Ja — worst case er at alle spørges. O(n).
Øvelse 3 — Indsæt element#
Hvor mange personer blev påvirket da den nye person kom ind i kæden?
Svar: 2 — de to naboer der skiftede hvem de holdt i skuldrene.
Hvad er kompleksiteten for selve indsættelsen? O(1)
Hvad kostede det at finde stedet i kæden inden indsættelsen?
Svar: du skulle tælle dig frem fra første person — O(n).
Hvad er den samlede kompleksitet? O(n)
Ville det gøre en forskel hvis personen skulle indsættes først eller sidst i kæden?
Ja — indsættelse forrest eller bagest kræver ingen traversering og er O(1) samlet.
Øvelse 4 — Slet element#
Hvor mange personer blev påvirket da personen forlod kæden?
Svar: 2 — de to naboer der tog fat i hinandens skuldre.
Hvad er kompleksiteten for selve sletningen? O(1)
Hvad kostede det at finde personen inden sletningen?
Svar: du skulle tælle dig frem fra første person — O(n).
Hvad er den samlede kompleksitet? O(n)
Ville det gøre en forskel hvis det var den første eller sidste person i kæden der skulle slettes?
Ja — sletning af første eller sidste element kræver ingen traversering og er O(1) samlet.