En informática , los casos mejor , peor y promedio de un algoritmo determinado expresan cuál es el uso de recursos al menos , como máximo y en promedio , respectivamente. Normalmente el recurso que se considera es el tiempo de ejecución, es decir, la complejidad del tiempo , 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 de los casos 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 informática 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. Menos extendido es el rendimiento en el mejor de los casos , 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 del peor de los casos. Los 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 el mejor resultado de una epidemia, la peor temperatura a la que está expuesto un elemento de un circuito electrónico, etc. Cuando se utilizan componentes de tolerancia especificada , los dispositivos deben diseñarse para funcionar correctamente con la peor combinación de casos. 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 caso para una búsqueda lineal simple en una lista ocurre 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: la mayoría de las empresas académicas y comerciales están más interesadas en mejorar la complejidad promedio y el peor desempeño . Los algoritmos también pueden modificarse trivialmente para tener un buen tiempo de ejecución en el mejor de los casos codificando soluciones para un conjunto finito de entradas, haciendo que la medida casi carezca de sentido. [1]
El análisis del desempeño en el peor de los casos y el análisis del desempeño en el caso promedio tienen algunas similitudes, pero en la práctica generalmente requieren herramientas y enfoques diferentes.
Determinar qué significa la entrada típica es difícil y, a menudo, esa entrada promedio tiene propiedades que dificultan su caracterización matemática (considérese, por ejemplo, los algoritmos que están diseñados para operar en cadenas de texto). De manera similar, incluso cuando es posible una descripción sensata de un "caso promedio" particular (que probablemente sólo será aplicable para algunos usos del algoritmo), tienden a resultar en un análisis de ecuaciones más difícil. [2]
El análisis del peor de los casos ofrece un análisis seguro (el peor de los casos nunca se subestima), pero puede ser demasiado pesimista , ya que puede que no haya aportaciones (realistas) que permitan dar 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 más al valor real pero que pueda ser optimista (quizás con alguna baja probabilidad 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 del caso promedio se llama análisis suavizado .
Al analizar algoritmos que a menudo tardan poco en completarse, pero que periódicamente requieren mucho más tiempo, se puede utilizar el análisis amortizado para determinar el tiempo de ejecución en el peor de los casos en una serie (posiblemente infinita) de operaciones . Este costo amortizado puede acercarse mucho más al costo promedio y al mismo tiempo ofrecer un límite superior garantizado en el tiempo de ejecución. Así, por ejemplo, los algoritmos en línea se basan frecuentemente en análisis amortizados.
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 los casos particulares que nos interesan sean promedio. Para la criptografía , esto es muy malo: queremos que los casos típicos de un problema criptográfico sean difíciles. Aquí se pueden utilizar métodos como la autorreducibilidad aleatoria para algunos problemas específicos para mostrar que el peor de los casos no es más difícil que el caso promedio o, de manera equivalente, 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 un comportamiento muy pobre 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 caída exponencial, por lo que el tiempo de ejecución de una operación está estadísticamente limitado.
