vergelijkingstijd

Vergelijkingstijd is de tijd die nodig is om een vergelijking tussen twee elementen uit te voeren, bijvoorbeeld bij sorteeralgoritmen of zoekalgoritmen. In informatica wordt vaak gesproken over de kost van een algoritme in termen van het aantal comparaties, omdat in veel toepassingen dit de dominante factor is.

In de analyse van algoritmen wordt de tijd vaak uitgedrukt als een combinatie van het aantal vergelijkingen en andere bewerkingen. Voor vergelijkinggebaseerde algoritmen bepaalt het aantal vergelijkingen doorgaans de orde van grootte van de tijdcomplexiteit. Er zijn verschillende scenario's: best-case, worst-case en gemiddelde situatie.

Factoren die de vergelijkingstijd beïnvloeden zijn onder meer het type data en de complexiteit van de vergelijking, de gebruikte datastructuur, en de computerarchitectuur (cache, geheugenhiërarchie, parallelisme) of programmeertaal. Zo kan het vergelijken van complexe sleutels aanzienlijk duurder zijn dan het vergelijken van eenvoudige primitieve typen.

Voorbeelden: sorteren. Quicksort en heapsort vereisen gemiddeld ongeveer n log2(n) vergelijkingen; mergesort komt in dezelfde orde uit. Insertion sort kan tot n(n-1)/2 vergelijkingen vereisen. Zoeken: binair zoeken vereist maximaal log2(n) + 1 vergelijkingen, lineair zoeken kan tot n vergelijkingen vereisen. Niet alle sortering vereist vergelijkingen: radix- of bucket-sort werkt zonder vergelijkingen.

Conclusie: vergelijkingstijd is een veelgebruikte maat voor prestatie in vergelijking-gebaseerde algoritmen, maar is slechts één factor van totale uitvoeringstijd; geheugen, schrijfbewerkingen en overhead spelen eveneens een belangrijke rol.