Complexitat temporal

En informàtica, la complexitat temporal és la complexitat computacional que descriu la quantitat de temps de l'ordinador que es necessita per executar un algorisme. La complexitat del temps s'estima habitualment comptant el nombre d'operacions elementals realitzades per l'algorisme, suposant que cada operació elemental triga un temps determinat a realitzar-se. Així, la quantitat de temps que es pren i el nombre d'operacions elementals realitzades per l'algorisme es considera que estan relacionades per un factor constant.Com que el temps d'execució d'un algorisme pot variar entre diferents entrades de la mateixa mida, normalment es considera la complexitat temporal del pitjor dels casos, que és la quantitat màxima de temps necessària per a entrades d'una mida determinada. Menys comú, i normalment s'especifica explícitament, és la complexitat del cas mitjà, que és la mitjana del temps que es prenen entrades d'una mida determinada (això té sentit perquè només hi ha un nombre finit d'entrades possibles d'una mida determinada). En ambdós casos, la complexitat temporal s'expressa generalment en funció de la mida de l'entrada. Com que aquesta funció és generalment difícil de calcular amb exactitud, i el temps d'execució per a entrades petites no sol ser conseqüent, normalment es centra en el comportament de la complexitat quan la mida de l'entrada augmenta, és a dir, el comportament asimptòtic de la complexitat. Per tant, la complexitat del temps s'expressa habitualment utilitzant la notació O gran, normalment $O(n)$, $O(n\log n)$, $O(n^{\alpha })$, $O(2^{n})$, etc., on n és la mida en unitats de bits necessària per representar l'entrada.

Gràfics de funcions que s'utilitzen habitualment en l' anàlisi d'algorismes, que mostren el nombre d'operacions N com a resultat de la mida d'entrada n per a cada funció

Les complexitats algorítmiques es classifiquen segons el tipus de funció que apareix a la notació O gran. Per exemple, un algorisme amb complexitat temporal $O(n)$ és un algorisme de temps lineal i un algorisme amb complexitat temporal $O(n^{\alpha })$ per alguna constant $\alpha >1$ és un algorisme de temps polinomial.

Taula de complexitats temporals comunes

La taula següent resumeix algunes classes de complexitats temporals que es troben habitualment. A la taula, poly(x) = x^O(1), és a dir, polinomi in x.

Nom	Complexitat	Temps d'execució(T(n))	Exemples
tempsconstant		$O(1)$	10
temps invers Ackermann		$O{\bigl (}\alpha (n){\bigr )}$
temps iteraactiu logarítmic		$O(\log ^{*}n)$
log-logarítmic		$O(\log \log n)$
temps logarítmic	DLOGTIME	$O(\log n)$	$\log n$, $\log(n^{2})$
temps polilogarítmic		${\text{poly}}(\log n)$	$(\log n)^{2}$
fractional power		$O(n^{c})$ where $0<c<1$	$n^{\frac {1}{2}}$, $n^{\frac {2}{3}}$
temps lineal		$O(n)$	n, $2n 5$
temps "n log-star n"		$O(n\log ^{*}n)$
temps linearítmic		$O(n\log n)$	$n\log n$, $\log n!$
temps quasilineal		$n{\text{poly}}(\log n)$	$n\log ^{2}n$
temps quadràtic		$O(n^{2})$	$n^{2}$
temps cúbic		$O(n^{3})$	$n^{3}$
temps polinomic	P	$2^{O(\log n)}={\text{poly}}(n)$	$n^{2} n$, $n^{10}$
temps quasi-polinomic	QP	$2^{{\text{poly}}(\log n)}$	$n^{\log \log n}$, $n^{\log n}$
temps sub-exponencial (primera definició)	SUBEXP	$O(2^{n^{\epsilon }})$ for all $\epsilon >0$
temps sub-exponencial (secona definició)		$2^{o(n)}$	$2^{\sqrt[{3}]{n}}$
temps exponencial (amb exponent lineal)	E	$2^{O(n)}$	$1.1^{n}$, $10^{n}$
temps exponencial	EXPTIME	$2^{{\text{poly}}(n)}$	$2^{n}$, $2^{n^{2}}$
temps factorial		$O(n!)$	$n!$
temps doble exponencial	2-EXPTIME	$2^{2^{{\text{poly}}(n)}}$	$2^{2^{n}}$