TuT O-notation
Læringsmål#
De studerende kan efter aktiviteten:
- Forklare hvad O-notation beskriver (vækstrate, ikke præcis tid)
- Knytte konkrete datastrukturer til deres tidskompleksitet
- Argumentere for forskellen på O(1), O(n) og O(log n) med fysiske eksempler
Forudsætninger#
De studerende forventes at kende til:
- Grundlæggende datastrukturer på konceptniveau (liste, stak)
- Begrebet “algoritme”
Kort beskrivelse#
De studerende roterer rundt til seks fysiske poster, der hver repræsenterer en datastruktur og en operation. Ved hver station udfører de en konkret handling og skriver deres bud på kompleksiteten i et svarark. Til sidst sammenlignes svar og der diskuteres fælles.
Pointen er at kompleksiteten skal erfares fysisk inden den formaliseres. Studerende der har stået i en menneskekæde og talt skridt ved godt hvad O(n) betyder.
Faglig kontekst#
- Semester/fag: Algorithms & Data Structures (valgfag)
- Holdstørrelse: Skalerer — justér antal studerende pr. station efter holdstørrelse
- Organisering: Grupper roterer mellem poster; svarark udfyldes i grupper
Poster#
De studerende får ikke at vide hvilke datastrukturer de forskellige poster repræsenterer. Senere skal de koble deres svarark til datastrukturer.
Post 1 — Array#
Operationer: Opslag på index, traversering, indsættelse og sletning. Pointen: Indexopslag er i konstant tid. Der er “faste pladser”, så indsættelse og sletning er i konstant tid.
Beskrivelse Post 1 - Array.
Post 2 — ArrayList#
Operationer: Opslag på index, traversering, indsættelse og sletning. Pointen: Forskel på at tilføje/slette midt i listen og i slutningen. Dynamisk størrelse.
Beskrivelse Post 2 - ArrayList.
Post 3 — Linked list#
Operation: Opslag på index, traversering, indsættelse og sletning.
Pointen: Opslag på index er ikke i konstant tid´, men det er indsættelse og sletning til gengæld.
Beskrivelse Post 3 - LinkedList.
Post 4 — Stack#
Operationer: Push, pop og søgning.
Pointen: Uanset størrelse på stak er push og pop i konstant tid.
Beskrivelse Post 4 - Stack
Post 5 — HashSet#
Operation: Søgning efter bestemt element, indsættelse og sletning
Pointen: Hvordan hashing fungerer og giver lav kompleksitet for alle operationer.
Beskrivelse Post 5 - HashSet
Station 6 — TreeSet#
Operation: Søg, indsæt og studerende i et træ baseret på fødselsdag (dag+måned). Gå til venstre hvis datoen er tidligere, til højre hvis den er senere.
Pointen: Hvordan kompleksistet afhænger af at træet er balanceret.
Beskrivelse Post 6 - TreeSet
Svarark#
Hver studerende får et svarark for hver post. De skriver deres bud på kompleksiteten. Opsamlingen tager udgangspunkt i svarene: hvad var I enige om? Hvad overraskede jer?
Tidsforbrug#
Med to hold á 7 studerende tog det en time.
Materialer#
Beskrevet under de forskellige poster men her er en samlet materialeliste
Modtagelse#
De studerende gik til opgaverne med godt humør og der var gode diskussioner undervejs. Studerende identificerede af sig selv nogle af datastrukturerne og havde snakke om “hvis det er var et array, så..” eller “Jamen er det så O(1) for det hele?? (i post 5 - hashset)”.
Post 6 om træstruktur var meget svær for dem at forstå. Det hjalp at de holdt snore mellem sig, så man kunne se hvilke noder der hang sammen.
Ved opsamlingen var de fleste enige om svarene og det blev tydeligt for alle at spørgsmålet “Ville det gøre en forskel hvis vi var 1000 i rækken/stakken” gav en kraftig indikation om hvad kompleksiteten var.
Udvidelser#
- De studerende skal matche de fysiske øvelser med datastrukturer
- De studerende implementerer de samme strukturer i Java og måler faktisk køretid
- Tilføj en station med O(n²) — f.eks. boblesortering med fysiske kort
- Lad studerende designe nye poster til medstuderende
Noter til underviseren#
Svarark er vigtig: forudsigelsen inden svaret er det der skaber det kognitive engagement. Lad grupperne diskutere før de afleverer — uenighed inden for gruppen er et godt tegn.