Complexitat temporal

De la Viquipèdia, l'enciclopèdia lliure
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ó

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]

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]

Taula de complexitats temporals comunes[modifica]

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

Referències[modifica]

  1. Sipser, Michael. Introduction to the Theory of Computation (en anglès). Course Technology Inc, 2006. ISBN 0-619-21764-2. 
  2. Team, Great Learning. «What is Time Complexity And Why Is It Essential?» (en anglès americà). https://www.mygreatlearning.com,+14-07-2022.+[Consulta: 17 agost 2023].
  3. «Understanding Time Complexity with Simple Examples» (en anglès americà), 14-11-2017. [Consulta: 17 agost 2023].
  4. «Big O Cheat Sheet – Time Complexity Chart» (en anglès). https://www.freecodecamp.org,+05-10-2022.+[Consulta: 17 agost 2023].