Handboek · hoofdstuk 34Algoritmen en complexiteit

Een algoritme beschrijft eindige, ondubbelzinnige stappen voor een klasse problemen. De specificatie legt invoer, uitvoer en uitzonderingen vast. ‘Zoek een temperatuur’ is onvolledig: zoek je een exact tijdstip, de eerste overschrijding of de dichtstbijzijnde waarde? Een correcte implementatie kan toch de verkeerde specificatie uitvoeren.

Drie bewijsstukken horen bij het ontwerp: een preconditie, een invariant tijdens de uitvoering en een postconditie. Lineair zoeken bewaart: alle eerder bekeken posities bevatten de gezochte sleutel niet. Wanneer een overeenkomst verschijnt, is de gevonden index juist; wanneer de lijst eindigt, is de sleutel afwezig. De lus eindigt omdat het aantal ongecontroleerde elementen telkens afneemt.

Lineair zoeken vraagt in het slechtste geval $n$ vergelijkingen. Binair zoeken vereist een gesorteerde reeks en snelle toegang tot het middelste element. Na een vergelijking blijft alleen een interval over: links als de sleutel kleiner is, rechts als hij groter is. Invariant: als de sleutel bestaat, ligt hij in het overblijvende interval.

Werk met een halfopen interval $[l,r)$: begin met $l=0$, $r=n$. Kies $m=(l+r)//2$. Bij een kleinere sleutel wordt $r=m$, bij een grotere $l=m+1$. Voor $l=r$ is het interval leeg. De verminderende intervalbreedte bewijst beëindiging, ook bij een lege lijst. Na $k$ halveringen blijven hoogstens $n/2^k$ elementen over: de groei is logaritmisch. Een gekoppelde lijst kent geen goedkope middentoegang; daar verdwijnt dit voordeel.

Invoegsorteren houdt links een gesorteerd prefix bij. Elk nieuw element schuift naar zijn plaats. Bij omgekeerde invoer zijn er $1+2+\cdots +(n-1)=n(n-1)/2$ verschuivingen: $O(n^2)$. Bij reeds gesorteerde invoer is het lineair. Het algoritme kan stabiel zijn: records met dezelfde sleutel behouden hun volgorde.

Mergesort splitst de lijst in tweeën, sorteert beide helften en voegt ze samen. Samenvoegen kost $O(n)$; op elke van ongeveer ${\log }_{2}n$ niveaus wordt in totaal $n$ werk gedaan. Dus $T(n)=2T(n/2)+O(n)=O(n\log n)$. Een gewone arrayimplementatie gebruikt tijdelijk $O(n)$ geheugen. Quicksort verdeelt rond een pivot: gemiddeld $O(n\log n)$, maar $O(n^2)$ bij slechte verdelingen. Een bibliotheeksortering is gewoonlijk verstandiger dan een eigen sorteerroutine, tenzij een meetbaar geheugen- of real-time contract anders vereist.

$f(n)=O(g(n))$ betekent: er bestaan $c>0$ en $n_0$ zodat $0\le f(n)\le cg(n)$ voor alle $n\ge n_0$. Constanten en lagere machten verdwijnen uit de groeiklasse: $3n^2+20n+7=O(n^2)$. Met $\Theta (n^2)$ zeg je ook dat de orde van onderen begrensd is. Een $O(n^2)$ algoritme is formeel tevens $O(n^3)$; daarom vermeld je de scherpste nuttige grens.

Een werkmodel moet benoemen wat telt: vergelijkingen, vermenigvuldigingen, bytes of berichten. Op de Mega kan geheugengebruik de doorslag geven; op de Pi kan netwerk-I/O belangrijker zijn dan rekenen. Dezelfde asymptotische klasse kan een factor honderd verschillen. Meet met herhalingen, geef invoergrootte en omstandigheden en gebruik de mediaan; een kleine proef bewijst geen worst-case grens.

Recursie heeft een basisgeval en een stap die aantoonbaar dichterbij dat geval komt. Voor faculteit: $0!=1$ en $n!=n(n-1)!$ voor geheel $n\ge 1$. De invoer moet gevalideerd worden; een negatieve n bereikt 0 nooit. Elke actieve aanroep bewaart een frame: bij faculteit zijn tijd en stapel beide $O(n)$. Een iteratieve lus gebruikt $O(1)$ extra geheugen.

De naïeve Fibonacci-recursie $F_n=F_{n-1}+F_{n-2}$ herberekent dezelfde deelproblemen. De aanroepboom groeit exponentieel. Memoïsatie bewaart elk resultaat eenmaal; dan worden tijd en geheugen $O(n)$. Een iteratieve oplossing bewaart alleen de vorige twee waarden. Deel-en-heers zoals mergesort is nuttige recursie, omdat de deelproblemen zonder deze explosieve overlap ontstaan.

Een kruising of meetplaats is een knoop; een berijdbare verbinding is een kant. De afstand is een gewicht. Eenrichtingsverkeer vraagt gerichte kanten. Verboden doorgangen haal je uit de graaf; een grote straf is ongeschikt als de route echt verboden is. Bij vaste snelheid is afstand een bruikbare doelfunctie; bij draaien, wachten en hellingen modelleer je reistijd of energie.

Een adjacentielijst bewaart per knoop de buren: $O(V+E)$ geheugen. Een adjacentiematrix kost $O(V^2)$ en biedt directe kantopzoeking. Niet elk paar knopen is verbonden; onbereikbaarheid hoort als oneindige afstand in de uitvoer. Het voorbeeld breidt de lusrobot van i33 uit met keuzeroutes, zonder de eerdere ganggeometrie als echte stationskaart te presenteren.

Begin met afstand 0 bij de bron en oneindig elders. Neem telkens de kleinste voorlopige afstand uit de prioriteitswachtrij. Relaxeer alle uitgaande kanten: $d(v)\leftarrow \min (d(v),d(u)+w(u,v))$. Bewaar bij een verbetering de voorganger. Het pad lees je achterwaarts terug.

Het correctheidsargument gebruikt niet-negatieve gewichten: een omweg door nog onbekende knopen kan een reeds kleinste afstand niet verkleinen. Met een negatieve kant breekt dat argument. Een heap biedt $O(\log V)$ per extractie of invoeging; met een gebruikelijke efficiënte implementatie is de tijd $O((V+E)\log V)$. Deze lescode laat oude heapkandidaten staan: bij verwerking worden ze verworpen. De heap kan dan $O(E)$ entries bewaren, met tijd $O((V+E)\log E)$; voor eenvoudige grafen is dit dezelfde gebruikelijke logaritmische orde.

Een kortste pad tussen twee knopen is een ander probleem dan een rondreis die alle inspectiepunten bezoekt. Het handelsreizigersprobleem heeft in een brute-force aanpak $n!$ volgordes; symmetrie kan dat aantal verkleinen, maar de groei blijft explosief. Voor drie punten zijn zes volgordes klein, voor twintig zijn het circa $2,43\cdot 10^{18}$.

Een heuristiek zoals telkens de dichtstbijzijnde onbezochte plek geeft snel een route, zonder garantie op het optimum. A* gebruikt een ondergrens op de resterende afstand: met een geschikte admissibele heuristiek blijft een optimale oplossing mogelijk. Bij veranderende obstakels moet de robot opnieuw plannen. Lokale obstakeldetectie en de noodstop blijven afzonderlijke functies: een optimale kaart mag nooit een actuele blokkade overrulen.