Mejor, peor y promedio caso
En informática , los casos mejores , peores y promedio de un algoritmo dado expresan cuál es el uso de recursos al menos , como máximo y en promedio , respectivamente. Por lo general, 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 u otro recurso. El mejor caso es la función que realiza el número mínimo de pasos en los 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 los datos de entrada de n elementos.
En la computación en tiempo real , el tiempo de ejecución en el peor de los casos es a menudo de particular 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 terminará a tiempo.
El rendimiento medio y el rendimiento en el peor de los casos son los más utilizados en el análisis de algoritmos. El desempeño en el mejor de los casos se encuentra menos ampliamente , pero tiene usos: por ejemplo, cuando se conocen los mejores casos de tareas individuales, se pueden usar 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 mejor resultado de una epidemia, la peor temperatura a la que está expuesto un elemento de circuito electrónico, etc. Cuando se utilizan componentes de tolerancia especificada , los dispositivos deben estar diseñados para funcionar correctamente con la combinación del peor de los 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 rendimiento del mejor caso: la mayoría de las empresas académicas y comerciales están más interesadas en mejorar la complejidad del caso medio y el rendimiento en el peor de los casos . Los algoritmos también pueden modificarse trivialmente para tener un buen tiempo de ejecución en el mejor de los casos mediante soluciones de codificación rígida para un conjunto finito de entradas, lo que hace que la medida sea casi sin sentido. [1]
