Idéer för aktivt lärande
Komplexitet och ordo-notation (Big O) är verktygen vi använder för att prata om hur en algoritm presterar när mängden data växer. Istället för att mäta sekunder, vilket beror på hårdvaran, mäter vi antalet operationer. Detta ger eleverna ett språk för att diskutera skalbarhet, vilket är kritiskt i en värld där datamängderna ständigt ökar.
Aktivitet 01
Eleverna kör två olika algoritmer för att lösa samma problem med indata av storlek 10, 100, 1000 och 10000. De prickar in resultaten i en graf för att visuellt se skillnaden mellan linjär och kvadratisk tillväxt.
Vad innebär Big O-notation?
Aktivitet 02
Läraren sätter upp olika kodsnuttar på väggarna. Eleverna går runt i par och försöker lista ut ordo-notationen för varje exempel och skriver sina gissningar och motiveringar på post-it-lappar.
Hur påverkar indatastorleken exekveringstiden?
Aktivitet 03
Eleverna får diskutera scenarier som att söka efter en person på Instagram vs att söka i en klasslista. De diskuterar varför en algoritm som fungerar för klassen skulle kunna 'krascha' internet om den användes globalt.
Hur skiljer sig tidskomplexitet från rumskomplexitet?
Några anteckningar om att undervisa detta avsnitt
Se upp för dessa missuppfattningar
Att Big O visar exakt hur många sekunder ett program tar.
Förklara att Big O beskriver tillväxttakten, inte den exakta tiden. Genom att köra samma kod på en gammal och en ny dator ser eleverna att ordo-notationen är densamma trots olika tider.
Att O(n^2) alltid är sämre än O(n).
Visa att för mycket små indata kan den kvadratiska algoritmen vara snabbare på grund av mindre förberedelser. Diskussioner kring 'konstanter' hjälper eleverna att se nyanserna.
Metoder som används i denna översikt
Introduktion till algoritmer
Eleverna introduceras till vad en algoritm är och hur man kan bryta ner komplexa problem i mindre, hanterbara delar. Fokus ligger på pseudokod och flödesscheman.
8 methodologies
Sorterings- och sökalgoritmer
Genomgång av klassiska algoritmer för sökning och sortering, såsom binärsökning och quicksort. Eleverna jämför deras effektivitet i olika scenarier.
8 methodologies