Svarark — Post 4 (facit)#
Øvelse 1 — Indsæt element (push)#
Hvor mange tallerkener blev påvirket da den nye tallerken blev lagt på?
Svar: 0 — den lægges bare øverst. Ingen andre rykker sig.
Hvad er kompleksiteten? O(1)
Ville det gøre en forskel hvis der var 1.000 tallerkener i stakken?
Nej — du lægger altid øverst. Stakkens størrelse er ligegyldig.
Øvelse 2 — Fjern element (pop)#
Hvor mange tallerkener blev påvirket da den øverste tallerken blev taget af?
Svar: 0 — du tager bare den øverste. Ingen andre rykker sig.
Hvad er kompleksiteten? O(1)
Ville det gøre en forskel hvis der var 1.000 tallerkener i stakken?
Nej — du tager altid den øverste. Stakkens størrelse er ligegyldig.
Øvelse 3 — Find specifikt element#
Hvor mange tallerkener skulle I tage af for at finde den rigtige?
Svar: varierer — afhænger af hvor langt nede i stakken elementet ligger.
Hvad ville worst case være hvis ordet ikke fandtes?
Svar: alle tallerkener skal tages af — O(n).
Hvad er kompleksiteten? O(n)
Ville det gøre en forskel hvis der var 1.000 tallerkener i stakken?
Ja — jo dybere elementet ligger, jo flere tallerkener skal tages af. Worst case er alle.