Idéer för aktivt lärande
Algoritmisk komplexitet och Big O-notation ger eleverna ett språk för att beskriva hur en algoritms resursförbrukning växer när indatan ökar. Detta är ett av de mest matematiska inslagen i kursen och kräver att eleverna kan tänka abstrakt kring tid och minne. Det är en kritisk färdighet för att kunna utvärdera om en lösning är skalbar i verkliga system.
Aktivitet 01
Sätt upp affischer med olika kodsnuttar runt om i rummet. Eleverna går runt i grupper, analyserar koden och markerar vilken Big O-kategori (t.ex. O(n) eller O(n²)) de anser att koden tillhör med en motivering.
Vad innebär Big O-notation?
Aktivitet 02
Eleverna kör program med nästlade loopar mot listor av storlek 10, 100, 1000 och 10000. De prickar in resultaten i ett diagram för att se om tillväxten är linjär eller kvadratisk, vilket bekräftar teorin bakom Big O.
Hur beräknar man tidskomplexiteten för en given algoritm?
Aktivitet 03
Dela klassen i två sidor. Den ena sidan argumenterar för att optimera tidskomplexitet till varje pris, medan den andra fokuserar på minneskomplexitet (rumskomplexitet). De får försvara sina positioner utifrån olika scenarier, som inbyggda system kontra molnservrar.
Varför är det viktigt att förstå algoritmisk effektivitet?
Några anteckningar om att undervisa detta avsnitt
Se upp för dessa missuppfattningar
Att Big O mäter exakt tid i sekunder.
Big O mäter hur antalet operationer växer i förhållande till indata, inte sekunder. Genom att köra samma kod på en snabb och en långsam dator ser eleverna att Big O-värdet förblir detsamma trots olika tider.
Att O(n²) alltid är sämre än O(n log n).
För mycket små datamängder kan en enklare algoritm med högre komplexitet vara snabbare på grund av lägre konstantfaktorer. Diskussioner kring 'verkliga' fall hjälper eleverna att se nyanserna.
Metoder som används i denna översikt
Linjära och icke-linjära datastrukturer
Undersökning av listor, köer, stackar, träd och grafer. Hur valet av datastruktur påverkar programmets prestanda.
8 methodologies
Sorterings- och sökalgoritmer
Analys och implementering av avancerade algoritmer som Quicksort, Mergesort och binärsökning.
8 methodologies