Caso mejor, peor y promedio
En informática , los casos mejor , peor 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 de los casos 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 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 terminará 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 ampliamente encontrado es el rendimiento del mejor de los casos , 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 el mejor de los casos de una epidemia, la temperatura del peor de los casos a la que se expone un elemento de un circuito electrónico, etc. 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 de los casos: la mayoría de las empresas académicas y comerciales están más interesadas en mejorar la complejidad del caso promedio 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 la codificación de soluciones para un conjunto finito de entradas, lo que hace que la medida casi no tenga sentido. [1]
