Indholdsfortegnelse

Svarark — Post 1 (facit)
#

Øvelse 1 — Opslag på index
#

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

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. Antallet af personer i rækken 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: 1 — kun den der stod der i forvejen forlader pladsen.

Hvad er kompleksiteten? O(1)

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

Nej — du overskriver bare én plads. Ingen andre påvirkes.

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

Svar: 0 — pladsen er nu tom (null). Ingen andre flytter sig.

Hvad er kompleksiteten? O(1)

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

Nej — du sætter bare pladsen til null. Ingen andre påvirkes.