Complejidad computacional asintótica

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 asociada con el uso de la notación O grande .

En lo que respecta a los recursos computacionales , se suelen estimar la complejidad temporal asintótica y la complejidad espacial asintótica de los algoritmos y programas computacionales. Otros comportamientos estimados asintóticamente incluyen la complejidad de los circuitos y diversas medidas de computación paralela , como el número de procesadores (paralelos).

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 vuelto comúnmente utilizado para referirse a la complejidad computacional asintótica.

Además, a menos que se especifique lo contrario, el término "complejidad computacional" generalmente se refiere a un límite superior para 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${\displaystyle O(n^{3}).}$Otros tipos de estimaciones de complejidad computacional (asintótica) son los límites inferiores ( notación " omega grande "; p. ej., Ω( n )) y las estimaciones asintóticamente ajustadas, cuando los límites superior e inferior asintóticos coinciden (escritos usando la notación " theta grande "; p. ej., Θ( n log n )).

Otra suposición tácita es que la complejidad en el peor de los casos está en entredicho 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 .

• Algoritmo asintóticamente óptimo