Mejor, peor y promedio de los casos

En informática , los casos mejor , peor y promedio de un algoritmo dado expresan cuál es el uso de recursos como mínimo , como máximo y como promedio , respectivamente. Por lo general, el recurso que se considera es el tiempo de ejecución, es decir, la complejidad temporal , pero también podría ser la memoria o algún otro recurso. El mejor caso es la función que realiza el número mínimo de pasos en datos de entrada de n elementos. El peor caso es la función que realiza el número máximo de pasos en datos de entrada de tamaño n. El caso promedio es la función que realiza un número promedio de pasos en datos de entrada de n elementos.

En la computación en tiempo real , el tiempo de ejecución en el peor de los casos suele ser motivo de especial preocupación, ya que es importante saber cuánto tiempo podría ser necesario en el peor de los casos para garantizar que el algoritmo siempre finalizará a tiempo.

El rendimiento promedio y el rendimiento en el peor de los casos son los más utilizados en el análisis de algoritmos. El rendimiento en el mejor de los casos es menos común , pero tiene usos: por ejemplo, cuando se conocen los mejores casos de tareas individuales, se pueden utilizar para mejorar la precisión de un análisis general en el peor de los casos. Los científicos informáticos utilizan técnicas de análisis probabilístico , especialmente el valor esperado , para determinar los tiempos de ejecución esperados.

Los términos se utilizan en otros contextos; por ejemplo, el peor y mejor resultado posible de una epidemia, la peor temperatura a la que está expuesto un elemento de un circuito electrónico, etc. Cuando se utilizan componentes con una tolerancia específica , los dispositivos deben estar diseñados para funcionar correctamente con la peor combinación de tolerancias y condiciones externas.

El término rendimiento en el mejor de los casos se utiliza en informática para describir el comportamiento de un algoritmo en condiciones óptimas. Por ejemplo, el mejor de los casos para una búsqueda lineal simple en una lista se produce cuando el elemento deseado es el primer elemento de la lista.

El desarrollo y la elección de algoritmos rara vez se basan en el mejor desempeño posible: la mayoría de las empresas académicas y comerciales están más interesadas en mejorar la complejidad promedio y el desempeño en el peor de los casos . Los algoritmos también pueden modificarse de manera trivial para que tengan un buen tiempo de ejecución en el mejor de los casos mediante la codificación rígida de soluciones para un conjunto finito de entradas, lo que hace que la medida casi no tenga sentido. ^[1]

El análisis del rendimiento en el peor de los casos y el análisis del rendimiento en el caso promedio tienen algunas similitudes, pero en la práctica generalmente requieren herramientas y enfoques diferentes.

Determinar qué significa una entrada típica es difícil y, a menudo, esa entrada promedio tiene propiedades que dificultan su caracterización matemática (pensemos, por ejemplo, en los algoritmos diseñados para operar con cadenas de texto). De manera similar, incluso cuando es posible una descripción sensata de un "caso promedio" particular (que probablemente solo será aplicable para algunos usos del algoritmo), tienden a dar como resultado un análisis de ecuaciones más difícil. ^[2]

El análisis del peor de los casos proporciona un análisis seguro (nunca se subestima el peor de los casos), pero que puede ser demasiado pesimista , ya que puede que no haya ninguna entrada (realista) que requiera tantos pasos.

En algunas situaciones puede ser necesario utilizar un análisis pesimista para garantizar la seguridad. Sin embargo, a menudo un análisis pesimista puede ser demasiado pesimista, por lo que un análisis que se acerque al valor real pero que sea optimista (quizás con una probabilidad baja conocida de falla) puede ser un enfoque mucho más práctico. Un enfoque moderno en la teoría académica para cerrar la brecha entre el análisis del peor de los casos y el análisis del caso promedio se denomina análisis suavizado .

Al analizar algoritmos que a menudo requieren poco tiempo para completarse, pero que periódicamente requieren un tiempo mucho mayor, se puede utilizar el análisis amortizado para determinar el tiempo de ejecución en el peor de los casos a lo largo de una serie (posiblemente infinita) de operaciones . Este costo amortizado puede ser mucho más cercano al costo promedio, al tiempo que proporciona un límite superior garantizado para el tiempo de ejecución. Por ejemplo, los algoritmos en línea se basan con frecuencia en el análisis amortizado.

El análisis del peor de los casos está relacionado con la complejidad del peor de los casos . ^[3]

Muchos algoritmos con un mal desempeño en el peor de los casos tienen un buen desempeño en el caso promedio. Para los problemas que queremos resolver, esto es algo bueno: podemos esperar que las instancias particulares que nos interesan sean promedio. Para la criptografía , esto es muy malo: queremos que las instancias típicas de un problema criptográfico sean difíciles. Aquí, métodos como la autorreducibilidad aleatoria se pueden usar para algunos problemas específicos para demostrar que el peor caso no es más difícil que el caso promedio o, equivalentemente, que el caso promedio no es más fácil que el peor caso.

Por otro lado, algunas estructuras de datos como las tablas hash tienen comportamientos muy pobres en el peor de los casos, pero una tabla hash bien escrita y de tamaño suficiente estadísticamente nunca dará el peor de los casos; el número promedio de operaciones realizadas sigue una curva de decaimiento exponencial y, por lo tanto, el tiempo de ejecución de una operación está estadísticamente limitado.

• Ordenación por inserción aplicada a una lista de n elementos, que se supone que son todos diferentes y que inicialmente están en orden aleatorio. En promedio, la mitad de los elementos de una lista A ₁ ... A _j son menores que el elemento A _{j +1} y la otra mitad son mayores. Por lo tanto, el algoritmo compara el elemento ( ^j +  1) que se insertará en promedio con la mitad de la sublista ya ordenada, por lo que t _j = j /2. Calcular el tiempo de ejecución del caso promedio resultante produce una función cuadrática del tamaño de entrada, al igual que el tiempo de ejecución del peor caso.
• Quicksort aplicado a una lista de n elementos, nuevamente asumiendo que todos son diferentes e inicialmente en orden aleatorio. Este popular algoritmo de ordenamiento tiene un rendimiento promedio de O( n  log( n )), lo que contribuye a convertirlo en un algoritmo muy rápido en la práctica. Pero dada una entrada en el peor de los casos, su rendimiento se degrada a O( n ² ). Además, cuando se implementa con la política de "primero el más corto", la complejidad espacial en el peor de los casos está limitada por O(log( n )).
• La ordenación por montículos requiere un tiempo O(n) cuando todos los elementos son iguales. La ordenación por montículos requiere un tiempo O(n) y, luego, la eliminación de elementos del montón requiere un tiempo O(1) para cada uno de los n elementos. El tiempo de ejecución aumenta a O(nlog(n)) si todos los elementos deben ser distintos.
• El ordenamiento de los elementos en la primera iteración tiene un tiempo O(n). En cada iteración se comprueba si todos los elementos están en orden. Hay n! permutaciones posibles; con un generador de números aleatorios balanceado, casi cada permutación de la matriz se obtiene en n! iteraciones. Las computadoras tienen una memoria limitada, por lo que los números generados se repiten en ciclos; puede que no sea posible alcanzar cada permutación. En el peor de los casos, esto conduce a un tiempo O(∞), un bucle infinito.

• Búsqueda lineal en una lista de n elementos. En el peor de los casos, la búsqueda debe visitar cada elemento una vez. Esto sucede cuando el valor buscado es el último elemento de la lista o no está en ella. Sin embargo, en promedio, suponiendo que el valor buscado está en la lista y que cada elemento de la lista tiene la misma probabilidad de ser el valor buscado, la búsqueda visita solo n /2 elementos.

• Algoritmo de ordenación : un área en la que hay una gran cantidad de análisis de rendimiento de varios algoritmos.
• Estructura de datos de búsqueda : cualquier estructura de datos que permita la recuperación eficiente de elementos específicos.
• Análisis del circuito en el peor de los casos
• Análisis suavizado
• Elemento finito de intervalo
• Notación O grande