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 termine 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 pueda ser optimista (quizás con una baja probabilidad de falla conocida) 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 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 mismo 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 de los casos 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 de los casos.
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.
