rekenefficiëntie

Rekenefficiëntie is een maat voor de hoeveelheid hulpbronnen die nodig is om een berekening uit te voeren. Meestal gaat het om tijd (CPU-tijd) en geheugen (RAM), maar ook energieverbruik kan worden meegewogen. Rekenefficiëntie wordt vaak gebruikt om verschillende algoritmen of implementaties met elkaar te vergelijken.

Om rekenefficiëntie te kwantificeren wordt vaak gesproken over tijdscomplexiteit en ruimtelijke complexiteit. Tijdscomplexiteit beschrijft hoe de benodigde tijd groeit met de grootte van de invoer. Ruimtelijke complexiteit beschrijft hoeveel geheugen wordt gebruikt. Zowel in worst-case als gemiddeldes, en soms als amortized analysis. Analyses gebeuren meestal met grote invoer (asymptotisch), maar praktijkmetingen op specifieke systemen zijn belangrijk voor realistische inschattingen.

In de praktijk wordt rekenefficiëntie bepaald door ontwerpkeuzes, datastructuren en hardware. Benchmarking en profilering meten werkelijke prestaties, maar verschillen per processor, geheugenbandbreedte en caching. Daarom worden zowel theoretische analyses als empirische metingen gebruikt. Voorbeelden zijn het verschil tussen een sorteeralgoritme met O(n log n) en een algoritme met O(n^2) bij grote invoer.

Effectieve maatregelen omvatten het kiezen van betere algoritmen en efficiëntere datastructuren, het verminderen van onnodig werk, en cachevriendelijke implementaties. Andere technieken zijn memoization, parallellisatie en vectorisatie, evenals energiezuinige praktijken op embedded systemen. Praktisch gezien is rekenefficiëntie vaak een afweging tussen snelheid, geheugen- en energieverbruik, afhankelijk van de context en vereisten van de toepassing.