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 estiman comúnmente la complejidad temporal asintótica y la complejidad espacial asintótica . Otros comportamientos estimados asintóticamente incluyen la complejidad del circuito y varias medidas de computación paralela , como la cantidad de procesadores (paralelos).

Desde el artículo innovador 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) ha pasado a denominarse comúnmente 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 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. Otros tipos de estimaciones de complejidad computacional (asintótica) son los límites inferiores (notación " Big Omega "; por ejemplo, Ω( n )) y las estimaciones asintóticamente ajustadas, cuando los límites superior e inferior asintóticos coinciden (escritos usando la " Big Theta "; por ejemplo, Θ( n log n )). ${\displaystyle O(n^{3}).}$

Otra suposición tácita es que el análisis del peor caso de complejidad computacional está en cuestión 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