En informática , se dice que un algoritmo es asintóticamente óptimo si, en términos generales, para entradas grandes su rendimiento es, en el peor de los casos, un factor constante (independientemente del tamaño de la entrada) peor que el del mejor algoritmo posible. Es un término que se encuentra con frecuencia en la investigación informática como resultado del uso generalizado de la notación big-O .
Más formalmente, un algoritmo es asintóticamente óptimo con respecto a un recurso particular si se ha demostrado que el problema requiere Ω( f ( n )) de ese recurso, y se ha demostrado que el algoritmo utiliza solo O( f ( n )).
Estas pruebas requieren la suposición de un modelo particular de cálculo , es decir, ciertas restricciones en las operaciones permitidas con los datos de entrada.
Como ejemplo simple, se sabe que todas las ordenaciones por comparación requieren al menos Ω( n log n ) comparaciones en el caso promedio y en el peor de los casos. Mergesort y heapsort son ordenaciones por comparación que realizan O( n log n ) comparaciones, por lo que son asintóticamente óptimas en este sentido.
Si los datos de entrada tienen algunas propiedades a priori que se pueden aprovechar en la construcción de algoritmos, además de las comparaciones, entonces pueden ser posibles algoritmos asintóticamente más rápidos. Por ejemplo, si se sabe que los N objetos son números enteros del rango [1, N ], entonces se pueden ordenar O( N ) veces, por ejemplo, mediante el método de ordenación por cubos .
Una consecuencia de que un algoritmo sea asintóticamente óptimo es que, para datos de entrada suficientemente grandes, ningún algoritmo puede superarlo en más de un factor constante. Por esta razón, los algoritmos asintóticamente óptimos suelen considerarse el "final del camino" en la investigación, la obtención de un resultado que no se puede mejorar drásticamente. Por el contrario, si un algoritmo no es asintóticamente óptimo, esto implica que, a medida que aumenta el tamaño de los datos de entrada, el algoritmo tiene un rendimiento cada vez peor que el mejor algoritmo posible.
En la práctica, resulta útil encontrar algoritmos que tengan un mejor rendimiento, incluso si no disfrutan de ninguna ventaja asintótica. Los nuevos algoritmos también pueden presentar ventajas, como un mejor rendimiento en entradas específicas, un menor uso de recursos o una mayor facilidad de descripción e implementación. Por lo tanto, los algoritmos asintóticamente óptimos no siempre son el "final del camino".
Si bien los algoritmos asintóticamente óptimos son resultados teóricos importantes, es posible que un algoritmo asintóticamente óptimo no se utilice en varias situaciones prácticas:
Un ejemplo de un algoritmo asintóticamente óptimo que no se utiliza en la práctica es el algoritmo de tiempo lineal de Bernard Chazelle para la triangulación de un polígono simple . Otro es la estructura de datos de matriz redimensionable publicada en "Resizable Arrays in Optimal Time and Space", [1] que puede indexar en tiempo constante pero en muchas máquinas conlleva una gran penalización práctica en comparación con la indexación de matrices ordinaria.
Formalmente, supongamos que tenemos un teorema de límite inferior que muestra que un problema requiere un tiempo Ω(f( n )) para resolverse para una instancia (entrada) de tamaño n (ver Notación Big O § Notación Big Omega para la definición de Ω). Entonces, se dice que un algoritmo que resuelve el problema en un tiempo O(f( n )) es asintóticamente óptimo. Esto también se puede expresar utilizando límites: supongamos que b( n ) es un límite inferior del tiempo de ejecución y que un algoritmo dado toma un tiempo t( n ). Entonces el algoritmo es asintóticamente óptimo si:
Este límite, si existe, es siempre al menos 1, ya que t( n ) ≥ b( n ).
Aunque generalmente se aplica a la eficiencia temporal, se puede decir que un algoritmo utiliza espacio asintóticamente óptimo, bits aleatorios, número de procesadores o cualquier otro recurso comúnmente medido utilizando la notación big-O.
A veces, las suposiciones vagas o implícitas pueden hacer que no quede claro si un algoritmo es asintóticamente óptimo. Por ejemplo, un teorema de límite inferior podría suponer un modelo de máquina abstracto particular , como en el caso de las clasificaciones por comparación, o una organización particular de la memoria. Al violar estas suposiciones, un nuevo algoritmo podría potencialmente superar asintóticamente el límite inferior y los algoritmos "asintóticamente óptimos".
La inexistencia de un algoritmo asintóticamente óptimo se llama aceleración. El teorema de aceleración de Blum muestra que existen problemas construidos artificialmente con la aceleración. Sin embargo, es un problema abierto si muchos de los algoritmos más conocidos hoy en día son asintóticamente óptimos o no. Por ejemplo, hay un algoritmo para encontrar árboles de expansión mínimos , donde es la inversa de crecimiento muy lento de la función de Ackermann , pero el límite inferior más conocido es el trivial . Se desconoce si este algoritmo es asintóticamente óptimo, y probablemente sería aclamado como un resultado significativo si se resolviera de cualquier manera. Coppersmith y Winograd (1982) demostraron que la multiplicación de matrices tiene una forma débil de aceleración entre una clase restringida de algoritmos (identidades bilineales de tipo Strassen con cálculo lambda).
