Ga naar hoofdinhoud

7.4 O(n) — lineaire tijd

Leerdoel: je herkent algoritmes waarvan het werk recht-evenredig groeit met n, en je ziet visueel een rechte schuine lijn.

Hoe gedraagt het zich?​

O(n) betekent: het werk schaalt mee met de invoer. Twee keer zoveel elementen → twee keer zoveel werk. Tien keer zoveel → tien keer zoveel.

Analogie: vakkenvullen in een supermarkt. Hoe meer pakken melk in de voorraad, hoe langer je bezig bent ze in het schap te zetten. Recht- evenredig.

Voorbeelden in Python​

sum(lijst)              # alles optellen — bekijkt elk element
max(lijst)              # grootste vinden — bekijkt elk element
doel in lijst           # zoeken — bekijkt elk element tot match
for x in lijst: ...     # door de hele lijst lopen

Bij elk van deze operaties moet Python in het slechtste geval alle elementen aanraken. Verdubbel de lijst → verdubbel het werk.

Voorspel​

We tellen het aantal vergelijkingen bij lineair zoeken naar een doel dat niet in de lijst staat (slechtste geval). Hoeveel stappen op een lijst van 100.000 elementen?

Antwoord

100.000 stappen. Het algoritme moet de hele lijst doorlopen om zeker te weten dat het doel er niet in staat. Slechtste geval = lengte van de lijst.

Run — kijk hoe het groeit​

Python
Code-omgeving wordt voorbereid…
Wat zie je?

Een rechte schuine lijn: stappen = n. Verdubbel n, verdubbel stappen.

Op log-log assen zou je een rechte lijn met helling 1 zien.

Welke algoritmes zijn O(n)?​

In dit curriculum:

Belangrijk: 2 vergelijkingen per element (zoals bij max-en-min) is nog steeds O(n), niet O(2n). Constanten tellen niet mee in Big O.

Door naar stap 5: O(log n) — logaritmisch →.