Algoritmo asintóticamente óptimo - Asymptotically optimal algorithm
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 entrada) peor que el mejor algoritmo posible. Es un término que se encuentra comúnmente en la investigación de la 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 usa solo O (f (n)).
Estas pruebas requieren la suposición de un modelo de cálculo particular , es decir, ciertas restricciones en las operaciones permitidas con los datos de entrada.
Como ejemplo simple, se sabe que todos los tipos de comparación requieren al menos comparaciones Ω ( n log n ) en el promedio y 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 pueden ordenarse O (N) tiempo, por ejemplo, por el tipo de cubo .
Una consecuencia de que un algoritmo sea asintóticamente óptimo es que, para entradas lo suficientemente grandes, ningún algoritmo puede superarlo en más de un factor constante. Por esta razón, los algoritmos óptimos asintóticamente se ven a menudo como el "final de la línea" en la investigación, el logro de un resultado que no se puede mejorar de manera espectacular. Por el contrario, si un algoritmo no es asintóticamente óptimo, esto implica que a medida que la entrada aumenta de tamaño, el algoritmo funciona 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, menor uso de recursos o ser más simples de describir e implementar. Por tanto, los algoritmos óptimos asintóticamente no siempre son el "final de la línea".
Aunque los algoritmos asintóticamente óptimos son resultados teóricos importantes, es posible que un algoritmo asintóticamente óptimo no se utilice en una serie de situaciones prácticas:
- Solo supera a los métodos más comúnmente utilizados para n más allá del rango de tamaños de entrada prácticos, como entradas con más bits de los que podrían caber en cualquier sistema de almacenamiento de computadora.
- Es demasiado complejo, por lo que la dificultad de comprenderlo e implementarlo correctamente supera su beneficio potencial en el rango de tamaños de entrada en consideración.
- Las entradas encontradas en la práctica caen en casos especiales que tienen algoritmos más eficientes o que los algoritmos heurísticos con malos tiempos en el peor de los casos pueden, no obstante, resolver de manera eficiente.
- En las computadoras modernas, las optimizaciones de hardware, como la memoria caché y el procesamiento en paralelo, pueden ser "interrumpidas" por un algoritmo asintóticamente óptimo (asumiendo que el análisis no tuvo en cuenta estas optimizaciones de hardware). En este caso, podría haber algoritmos subóptimos que hagan un mejor uso de estas características y superen a un algoritmo óptimo en datos realistas.
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 "Matrices redimensionables en tiempo y espacio óptimos", 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.
Definiciones formales
Formalmente, suponga que tenemos un teorema de límite inferior que muestra que un problema requiere Ω (f ( n )) tiempo para resolver una instancia (entrada) de tamaño n (consulte la notación O grande para la definición de Ω). Entonces, se dice que un algoritmo que resuelve el problema en O (f ( n )) tiempo es asintóticamente óptimo. Esto también se puede expresar usando límites: suponga que b ( n ) es un límite inferior en el tiempo de ejecución, y un algoritmo dado toma el tiempo t ( n ). Entonces el algoritmo es asintóticamente óptimo si:
Tenga en cuenta que 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 usa espacio asintóticamente óptimo, bits aleatorios, número de procesadores o cualquier otro recurso medido comúnmente usando 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 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 estas suposiciones, un nuevo algoritmo podría potencialmente superar asintóticamente el límite inferior y los algoritmos "asintóticamente óptimos".
Acelerar
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 en la actualidad son asintóticamente óptimos o no. Por ejemplo, existe un algoritmo O ( n α ( n )) para encontrar árboles de expansión mínimos , donde α ( n ) es la inversa de crecimiento muy lento de la función de Ackermann , pero el límite inferior más conocido es el trivial Ω ( n ) . Se desconoce si este algoritmo es asintóticamente óptimo y es probable que se aclamara 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 computación lambda).