Análisis asintótico

El análisis asintótico describe cómo el tiempo de ejecución o la memoria de un algoritmo crece a medida que el tamaño de la entrada se vuelve grande, utilizando notaciones como big-O, big-Omega y big-Theta para capturar la tasa de crecimiento, ignorando las constantes y los términos de orden inferior.

Definition

El análisis asintótico es la caracterización de la tasa de crecimiento de una función a medida que su argumento tiende al infinito; en el análisis de algoritmos, expresa cómo el uso de tiempo o espacio escala con el tamaño de la entrada, utilizando una notación de orden que suprime los factores constantes y los términos de orden inferior.

Scope

Este tema cubre las notaciones asintóticas utilizadas para caracterizar el uso de recursos — big-O (límite superior), big-Omega (límite inferior), big-Theta (límite ajustado), y las estrictas little-o y little-omega — junto con las clases de crecimiento estándar (constante, logarítmica, lineal, linealítmica, polinómica, exponencial) y las reglas para manipular estos límites. Trata por qué los factores constantes y los términos de orden inferior se abstraen y cómo las comparaciones asintóticas predicen el comportamiento de escalado. Excluye la maquinaria de resolución de recurrencias utilizada para obtener estos límites, cubierta por separado.

Core questions

• ¿Qué afirma cada una de las notaciones big-O, big-Omega y big-Theta sobre el crecimiento de una función?
• ¿Por qué se ignoran los factores constantes y los términos de orden inferior en la comparación asintótica?
• ¿Cómo se ordenan las clases de crecimiento comunes de más lento a más rápido crecimiento?
• ¿Cómo predicen los límites asintóticos cómo un algoritmo escala a grandes entradas?
• ¿Cuándo pueden los algoritmos asintóticamente más lentos seguir siendo preferibles en la práctica?

Key concepts

• notación big-O
• notación big-Omega
• notación big-Theta
• little-o y little-omega
• clases de crecimiento
• factores constantes
• términos de orden inferior
• escalabilidad

Key theories

Notación de orden

Big-O acota una función por encima dentro de un factor constante, big-Omega la acota por debajo, y big-Theta la acota en ambos sentidos; estas definiciones, estandarizadas para la informática por Knuth, proporcionan un lenguaje preciso para las tasas de crecimiento.

Dominancia de las tasas de crecimiento

A medida que el tamaño de la entrada crece, los términos de orden superior dominan, por lo que la clase asintótica de un algoritmo (por ejemplo, linealítmica versus cuadrática) determina en última instancia su escalabilidad, independientemente de los factores constantes.

Clinical relevance

La notación asintótica es la lingua franca para discutir la eficiencia de los algoritmos: permite a los ingenieros comparar algoritmos candidatos, predecir si un sistema escalará a cargas de trabajo más grandes y comunicar garantías de rendimiento en la documentación, entrevistas y el análisis de bibliotecas y estándares.

History

Las notaciones big-O y relacionadas se originaron en la teoría analítica de números del siglo XIX con Bachmann y Landau (de ahí 'notación de Landau'). Donald Knuth las adaptó y estandarizó para el análisis de algoritmos en las décadas de 1960 y 1970, incluyendo una nota de 1976 que aclaraba el uso de big-Omega y big-Theta en la informática.

Key figures

• Donald Knuth
• Paul Bachmann
• Edmund Landau

Seminal works

• knuth1976bigo
• cormen2009

Frequently asked questions

¿Un big-O más pequeño siempre significa un algoritmo más rápido?

No necesariamente para un tamaño de entrada dado. Big-O describe el crecimiento a medida que el tamaño de la entrada tiende al infinito y oculta los factores constantes, por lo que un algoritmo con una clase asintótica peor puede ser más rápido en entradas pequeñas. Es la mejor guía para entradas grandes y escalabilidad.

¿Cuál es la diferencia entre big-O y big-Theta?

Big-O solo proporciona un límite superior para el crecimiento, por lo que establece que el algoritmo no es peor que una tasa dada. Big-Theta proporciona un límite ajustado, afirmando que el crecimiento coincide con esa tasa tanto por encima como por debajo. Decir que un algoritmo es Theta(n log n) es una afirmación más fuerte y precisa que O(n log n).