Datalogi · Gymnasiet 2 · Algoritmer och problemlösning · 1.º Período

Komplexitet och ordo-notation

En djupdykning i hur man mäter algoritmers prestanda med hjälp av Big O-notation. Eleverna lär sig analysera tid- och rumskomplexitet.

Kort sammanfattning: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.

• Skolverket Kursplaner
• DAODAT0 - 2. Analys av algoritmer
• DAODAT0 - 4. Problemlösning

Om detta ämne

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.

I kursen Datalogi introduceras detta för att eleverna ska kunna göra välgrundade val i sin programkonstruktion. Vi tittar på tidskomplexitet (hur lång tid det tar) och rumskomplexitet (hur mycket minne som krävs). Att förstå skillnaden mellan en linjär ökning och en exponentiell är ofta en ögonöppnare för hur snabbt ett dåligt skrivet program kan bli oanvändbart.

Detta abstrakta koncept blir mer tillgängligt när eleverna får experimentera med stora datamängder och se hur exekveringstiden förändras i praktiken genom kollaborativa undersökningar.

Nyckelfrågor

1. Vad innebär Big O-notation?
2. Hur påverkar indatastorleken exekveringstiden?
3. Hur skiljer sig tidskomplexitet från rumskomplexitet?

Se upp för dessa missuppfattningar

Vanlig missuppfattning

Att Big O visar exakt hur många sekunder ett program tar.

Vad man ska lära ut istället

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.

Vanlig missuppfattning

Att O(n^2) alltid är sämre än O(n).

Vad man ska lära ut istället

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.

Idéer för aktivt lärande

Utforskande cirkel

Tidtagningsexperimentet

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.

40 min·Smågrupper

Gallergång

Komplexitets-galleriet

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.

30 min·Par

EPA (Enskilt-Par-Alla)

Verklighetens skalbarhet

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.

15 min·Par

Vanliga frågor

Måste eleverna kunna räkna ut komplexitet för alla typer av kod?

Nej, fokus ligger på att känna igen de vanligaste klasserna som konstant, linjär, logaritmisk och kvadratisk tid. Det viktiga är att de förstår principen för hur loopar och nästlade loopar påverkar prestandan.

Hur kan studentcentrerat lärande underlätta förståelsen av Big O?

Eftersom Big O är mycket abstrakt hjälper det att använda stationer där eleverna får utföra fysiska uppgifter (som att sortera papper) i olika skalor. När de själva känner hur arbetsbördan exploderar vid en kvadratisk algoritm, får de en intuitiv förståelse som är svår att nå via enbart föreläsning.

Varför är rumskomplexitet relevant idag när minne är billigt?

Även om minne är billigt är det inte oändligt, särskilt i inbyggda system eller vid hantering av Big Data. Att förstå rumskomplexitet lär eleverna att skriva resurssnål kod, vilket är en viktig del av god programkonstruktion enligt kursplanen.

Vilka matematiska begrepp bör eleverna vara bekanta med?

Grundläggande förståelse för funktioner och grafer är nödvändigt. Det underlättar också om de har en aning om logaritmer, men man kan ofta förklara det visuellt genom att visa hur man halverar en sökyta.