En informática , se dice que un algoritmo es asintóticamente óptimo si, en términos generales, para entradas grandes realiza, en el peor de los casos, un factor constante (independiente del tamaño de la entrada) peor que el mejor algoritmo posible. Es un término que se encuentra comúnmente en la investigación en ciencias de la computación como resultado del uso generalizado de la notación O grande .
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 usa solo O( f ( n )).
Estas pruebas requieren la suposición de un modelo particular de cálculo , es decir, ciertas restricciones sobre las operaciones permitidas con los datos de entrada.
Como ejemplo simple, se sabe que todos los tipos de comparación requieren al menos Ω( n log n ) comparaciones en el promedio y en el peor de los casos. Mergesort y heapsort son tipos de comparación que realizan comparaciones O ( n log n ) , por lo que son asintóticamente óptimos en este sentido.
Si los datos de entrada tienen algunas propiedades a priori que pueden explotarse 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, por clasificación de cubo .
Una consecuencia de que un algoritmo sea asintóticamente óptimo es que, para entradas suficientemente grandes, ningún algoritmo puede superarlo por más que un factor constante. Por esta razón, los algoritmos asintóticamente óptimos a menudo se consideran el "final del camino" en la investigación, la obtención de un resultado que no se puede mejorar dramáticamente. Por el contrario, si un algoritmo no es asintóticamente óptimo, esto implica que a medida que la entrada crece en tamaño, el algoritmo se desempeña cada vez peor que el mejor algoritmo posible.
En la práctica, es útil encontrar algoritmos que funcionen mejor, 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 ser más sencillos de describir e implementar. Por tanto, los algoritmos asintóticamente óptimos no siempre son el "final de la línea".
Aunque los algoritmos asintóticamente óptimos son resultados teóricos importantes, es posible que no se utilicen en varias situaciones prácticas:
Un ejemplo de 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 . Otra 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 Ω(f( n )) tiempo para resolverse para una instancia (entrada) de tamaño n (consulte Notación Big O § Notación Big Omega para conocer la definición de Ω) . Entonces, se dice que un algoritmo que resuelve el problema en tiempo O(f( n )) es asintóticamente óptimo. Esto también se puede expresar usando límites: supongamos que b( n ) es un límite inferior en el 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 del tiempo, se puede decir que un algoritmo utiliza espacio asintóticamente óptimo, bits aleatorios, número de procesadores o cualquier otro recurso comúnmente medido usando notación O grande.
A veces, suposiciones vagas o implícitas pueden hacer que no quede claro si un algoritmo es asintóticamente óptimo. Por ejemplo, un teorema del límite inferior podría asumir un modelo de máquina abstracto particular , como en el caso de los tipos de comparación, o una organización particular de la memoria. Al violar estos supuestos, un nuevo algoritmo podría potencialmente superar asintóticamente al límite inferior y a los algoritmos "asintóticamente óptimos".
La inexistencia de un algoritmo asintóticamente óptimo se denomina aceleración. El teorema de aceleración de Blum muestra que existen problemas de aceleración construidos artificialmente. 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, existe un algoritmo para encontrar árboles de expansión mínimos , donde es la inversa de la función de Ackermann que crece muy lentamente , 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 tipo Strassen con cálculo lambda).
