En la teoría de la complejidad computacional , la complejidad computacional asintótica es el uso del análisis asintótico para la estimación de la complejidad computacional de algoritmos y problemas computacionales , comúnmente asociado con el uso de la notación O grande .
Con respecto a los recursos computacionales , comúnmente se estiman la complejidad del tiempo asintótica y la complejidad del espacio asintótico . Otro comportamiento estimado asintóticamente incluye la complejidad del circuito y varias medidas de computación en paralelo , como el número de procesadores (en paralelo).
Desde el innovador artículo de 1965 de Juris Hartmanis y Richard E. Stearns [1] y el libro de 1979 de Michael Garey y David S. Johnson sobre NP-completitud , [2] el término " complejidad computacional " (de algoritmos) se ha convertido en comúnmente conocida como complejidad computacional asintótica.
Además, a menos que se especifique lo contrario, el término "complejidad computacional" generalmente se refiere al límite superior de la complejidad computacional asintótica de un algoritmo o un problema, que generalmente se escribe en términos de la notación O grande, por ejemplo. Otros tipos de estimaciones de complejidad computacional (asintóticas) son los límites inferiores ( notación " Big Omega "; por ejemplo, Ω( n )) y estimaciones asintóticamente ajustadas, cuando los límites asintóticos superior e inferior coinciden (escritos usando la " gran Theta "; por ejemplo, Θ( norte iniciar sesión norte )).
Otra suposición tácita es que el análisis del peor de los casos de complejidad computacional está en duda, a menos que se indique lo contrario. Un enfoque alternativo es el análisis probabilístico de algoritmos .
En la mayoría de los casos prácticos se discuten algoritmos deterministas o algoritmos aleatorios , aunque la informática teórica también considera algoritmos no deterministas y otros modelos avanzados de computación .
