19. Análisis asintótico de algoritmos

El análisis asintótico de algoritmos es una herramienta fundamental en ciencias de la computación que permite estudiar el comportamiento del costo computacional de un algoritmo cuando el tamaño de la entrada crece, ignorando constantes y detalles de implementación. Su objetivo principal no es medir tiempos exactos, sino comparar la eficiencia de algoritmos de manera general y teórica.

Desde una perspectiva formal, el análisis asintótico se centra en cómo crecen las funciones de tiempo o espacio en función del tamaño de la entrada nnn, especialmente cuando n→∞n \to \inftyn→∞. Esto es crucial porque en problemas reales los datos suelen ser grandes, y los factores constantes pierden relevancia frente al crecimiento del orden del algoritmo.

Idea central del análisis asintótico

Supongamos que un algoritmo tiene un tiempo de ejecución expresado como una función:

$$T(n)=3n2+5n+10$$

Aunque esta función describe con precisión el número de operaciones, el análisis asintótico se queda solo con el término dominante:

$$T(n)∼n2T(n) \sim n^2T(n)∼n2$$

Esto se debe a que, para valores grandes de nnn, los términos 5n5n5n y 101010 son insignificantes frente a n2n^2n2. Así, el algoritmo se clasifica como cuadrático.

---

Notaciones asintóticas principales

El análisis asintótico utiliza notaciones matemáticas para acotar el crecimiento de una función.

Big-O (OOO)
Describe una cota superior del tiempo o espacio requerido por un algoritmo. Representa el peor caso.

$$T(n)=O(f(n))T(n) = O(f(n))T(n)=O(f(n))$$

Significa que existe una constante ccc tal que:

undefined