Algoritmo asintóticamente óptimo

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 (independiente del tamaño de la entrada) peor que el de cualquier otro algoritmo posible. Este término se utiliza comúnmente en la investigación informática debido al uso generalizado de la notación de la gran O.

De manera más formal, 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 demostraciones requieren la suposición de un modelo de computación particular , es decir, ciertas restricciones en las operaciones permitidas con los datos de entrada.

Como ejemplo sencillo, se sabe que todos los algoritmos de ordenación 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 algoritmos de ordenación por comparación que realizan O ( n log n ) comparaciones, por lo que son asintóticamente óptimos en este sentido.

Si los datos de entrada tienen algunas propiedades a priori que se pueden explotar en la construcción de algoritmos, además de las comparaciones, entonces es posible que existan algoritmos asintóticamente más rápidos. Por ejemplo, si se sabe que los N objetos son enteros (no necesariamente distintos) del rango [1, N ], entonces se pueden ordenar en tiempo O ( N ) , por ejemplo, mediante el ordenamiento por cubetas .

Una consecuencia de que un algoritmo sea asintóticamente óptimo es que, para entradas suficientemente grandes, ningún otro algoritmo puede superarlo por más de un factor constante. Por esta razón, los algoritmos asintóticamente óptimos suelen considerarse el punto culminante de la investigación, un resultado que no puede mejorarse drásticamente. Por el contrario, si un algoritmo no es asintóticamente óptimo, esto implica que, a medida que aumenta el tamaño de la entrada, su rendimiento es cada vez peor que el de los mejores algoritmos posibles.

En la práctica, resulta útil encontrar algoritmos con mejor rendimiento, incluso si no presentan ninguna ventaja asintótica. Los nuevos algoritmos también pueden ofrecer ventajas como un mejor rendimiento con entradas específicas, un menor consumo de otros recursos o una mayor simplicidad en su descripción e implementación. Por lo tanto, los algoritmos asintóticamente óptimos no siempre representan la solución definitiva.

Si bien los algoritmos asintóticamente óptimos son resultados teóricos importantes, un algoritmo asintóticamente óptimo podría no utilizarse en diversas situaciones prácticas:

• Solo supera a los métodos más comúnmente utilizados para valores de n que están fuera 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 informático .
• 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 que se están considerando.
• Los datos de entrada que se encuentran en la práctica se enmarcan en casos especiales que cuentan con algoritmos más eficientes o que, aun con tiempos de ejecución en el peor de los casos elevados, pueden resolverse de manera eficiente mediante algoritmos heurísticos .
• En los ordenadores modernos, las optimizaciones de hardware , como la memoria caché y el procesamiento paralelo, pueden verse comprometidas por un algoritmo asintóticamente óptimo (siempre que el análisis no haya tenido en cuenta dichas optimizaciones). En este caso, podrían existir algoritmos subóptimos que aprovechen mejor estas características y superen el rendimiento de un algoritmo óptimo con datos reales.

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 . Otro ejemplo 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 penalización práctica considerable en comparación con la indexación de matrices ordinaria.

Formalmente, supongamos que tenemos un teorema de cota inferior que demuestra que un problema requiere un tiempo Ω( f ( n )) para resolverse para una instancia (entrada) de tamaño n (véase la notación Big O §  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.

Aunque se suele aplicar a la eficiencia temporal, se puede decir que un algoritmo utiliza de forma asintóticamente óptima espacio, bits aleatorios, número de procesadores o cualquier otro recurso que se mida habitualmente utilizando la notación de la gran O.

En ocasiones, las suposiciones vagas o implícitas pueden dificultar la determinación de si un algoritmo es asintóticamente óptimo. Por ejemplo, un teorema de cota inferior podría asumir un modelo de máquina abstracto específico , como en el caso de los algoritmos de ordenación por comparación, o una organización de memoria particular. Al incumplir estas suposiciones, un nuevo algoritmo podría superar asintóticamente tanto la cota inferior como los algoritmos considerados "asintóticamente óptimos".

La inexistencia de un algoritmo asintóticamente óptimo se denomina aceleración. El teorema de aceleración de Blum demuestra que existen problemas construidos artificialmente con aceleración. Sin embargo, sigue siendo un problema abierto si muchos de los algoritmos más conocidos en la actualidad son asintóticamente óptimos o no. Por ejemplo, existe un${\displaystyle O(n\alpha (n))}$algoritmo para encontrar árboles de expansión mínima , donde${\displaystyle \alpha (n)}$es la inversa de crecimiento muy lento de la función de Ackermann , pero la cota inferior más conocida es la trivial${\displaystyle \Omega (n)}$Se desconoce si este algoritmo es asintóticamente óptimo, y su resolución, en cualquier caso, probablemente se consideraría un resultado significativo. Coppersmith y Winograd (1982) demostraron que la multiplicación de matrices presenta una aceleración débil dentro de una clase restringida de algoritmos (identidades bilineales de tipo Strassen con cálculo lambda).

• Problema de unicidad de elementos
• Complejidad computacional asintótica