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.[1] :226Com 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 , , , , etc., on n és la mida en unitats de bits necessària per representar l'entrada.[2]
![Thumb](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7e/Comparison_computational_complexity.svg/320px-Comparison_computational_complexity.svg.png)
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 és un algorisme de temps lineal i un algorisme amb complexitat temporal per alguna constant és un algorisme de temps polinomial.[3]
La taula següent resumeix algunes classes de complexitats temporals que es troben habitualment. A la taula, poly(x) = xO(1), és a dir, polinomi in x.[4]
Nom | Complexitat | Temps d'execució(T(n)) | Exemples |
---|---|---|---|
tempsconstant | 10 | ||
temps invers Ackermann | |||
temps iteraactiu logarítmic | |||
log-logarítmic | |||
temps logarítmic | DLOGTIME | , | |
temps polilogarítmic | |||
fractional power | where | , | |
temps lineal | n, | ||
temps "n log-star n" | |||
temps linearítmic | , | ||
temps quasilineal | |||
temps quadràtic | |||
temps cúbic | |||
temps polinomic | P | , | |
temps quasi-polinomic | QP | , | |
temps sub-exponencial
(primera definició) |
SUBEXP | for all | |
temps sub-exponencial
(secona definició) |
|||
temps exponencial
(amb exponent lineal) |
E | , | |
temps exponencial | EXPTIME | , | |
temps factorial | |||
temps doble exponencial | 2-EXPTIME |
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.