Exponentiële tijd

In de computationele complexiteitstheorie is exponentiële tijd een complexiteitsgraad. Een algoritme wordt in exponentiële tijd uitgevoerd als de benodigde tijd, uitgedrukt als functie van de grootte van de invoer, wordt begrensd door een exponentiële functie. Als de grootte van de invoer, aangeduid met $n$, lineair stijgt dan stijgt de benodigde tijd om het algoritme uit te voeren exponentieel in $n$. Exponentiële tijd wordt ook genoteerd als $O(k^{n})$, waarbij $k$ een constante is, bijvoorbeeld $O(2^{n})$.

Een algoritme, waar exponentiële tijd voor nodig is om het uit te voeren, heeft bij voldoende invoer meer tijd nodig dan een algoritme, dat hetzelfde in polynomiale tijd doet.

Websites

• What is: Exponential Time Hypothesis.

· ·

Tijdcomplexiteit van algoritmen

constante tijd · lineaire tijd · polynomiale tijd · exponentiële tijd