miniatura|290x290px|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. 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 etc., on és la mida en unitats de bits necessària per representar l'entrada.
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.
Taula de complexitats temporals comunes La taula següent resumeix algunes classes de complexitats temporals que es troben habitualment. A la taula, , és a dir, polinomi in x. NomComplexitatTemps d'execucióExemplestempsconstant10temps invers Ackermanntemps iteraactiu logarítmiclog-logarítmictemps logarítmicDLOGTIME, temps polilogarítmicfractional power where , temps lineal, temps "n log-star n"temps linearítmic, temps quasilinealtemps quadràtictemps cúbictemps polinomicP, temps quasi-polinomicQP, temps sub-exponencial (primera definició)SUBEXP for all temps sub-exponencial (secona definició)temps exponencial (amb exponent lineal)E, temps exponencialEXPTIME, temps factorialtemps doble exponencial2-EXPTIME
Referències
Categoria:Complexitat computacional