Efficiëntie: hoeveel werk doet een algoritme?

Een programma dat bij tien items snel is, kan bij tienduizend items minuten duren. Efficiëntie gaat over die vraag: hoe groeit het werk als de invoer groeit?

Tellen hoeveel stappen

Zoek je een naam in een ongesorteerde lijst, dan moet je in het slechtste geval alle namen bekijken: bij duizend namen duizend stappen. Dat noemen we lineair: twee keer zoveel invoer, twee keer zoveel werk. Bubble sort, het sorteeralgoritme van level 2 op planeet Progio, vergelijkt elk paar buren steeds opnieuw: bij duizend items ongeveer een miljoen vergelijkingen. Twee keer zoveel invoer, vier keer zoveel werk: kwadratisch.

Slimmer zoeken

Is de lijst gesorteerd, dan kun je in het midden kijken en de helft weggooien: binair zoeken. Duizend namen kost dan hoogstens tien stappen, een miljoen namen twintig. Dat is het verschil tussen "de hele telefoongids doorlezen" en "in het midden openslaan". Sorteren kost eerst wat werk, maar daarna is elke zoekopdracht bijna gratis; daarom sorteert een database zijn gegevens.

Waarom dit belangrijk is

Op de opdrachten van Progio merk je het verschil niet: een lijst van tien getallen sorteert elke methode in een oogwenk. Maar dezelfde code in een app met miljoenen gebruikers wel. Informatici drukken groei uit met de "grote O": O(n) lineair, O(n²) kwadratisch, O(log n) logaritmisch. Je hoeft die notatie niet uit je hoofd te leren om het idee te snappen: tel hoeveel keer je door de invoer heen gaat, en of dat aantal meegroeit.

Efficiëntie in Progio

De sterren van Progio belonen bij blokken en turtle-opdrachten al korte oplossingen (een herhaling in plaats van tien losse regels). Op planeet Progio schrijf je zelf zoeken en sorteren, en bij recursie zie je hoe een elegant idee (Fibonacci) toch traag kan zijn omdat het hetzelfde werk steeds overdoet. Zie ook algoritme en lijst.