Hispanopedia Wiki
Articulo de referencia

Mejor caso, peor caso y caso promedio

En informática , los casos óptimo , pesimista y promedio de un algoritmo dado expresan el uso de recursos como mínimo , máximo y promedio , respectivamente. Generalmente, el rec...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , los casos óptimo , pesimista y promedio de un algoritmo dado expresan el uso de recursos como mínimo , máximo y promedio , respectivamente. Generalmente, el recurso considerado es el tiempo de ejecución, es decir, la complejidad temporal , pero también podría ser la memoria u otro recurso. El caso óptimo es la función que realiza el número mínimo de pasos sobre datos de entrada de n elementos. El caso pesimista es la función que realiza el número máximo de pasos sobre datos de entrada de tamaño n. El caso promedio es la función que realiza un número promedio de pasos sobre datos de entrada de n elementos. [ 1 ]

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 aplicaciones: 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 previstos.

Estos términos se utilizan en otros contextos; por ejemplo, para referirse al peor y al mejor escenario posible de una epidemia, a la temperatura máxima a la que se expone un elemento de un circuito electrónico, etc. Cuando se utilizan componentes con tolerancias específicas , los dispositivos deben diseñarse para funcionar correctamente con la peor combinación de tolerancias y condiciones externas.

Rendimiento óptimo del algoritmo

El término "rendimiento en el mejor caso" 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 se produce cuando el elemento deseado es el primero de la lista.

El desarrollo y la selección de algoritmos rara vez se basan en el rendimiento en el mejor de los casos: la mayoría de las empresas académicas y comerciales están más interesadas en mejorar la complejidad en el caso promedio y el rendimiento en el peor de los casos . Los algoritmos también pueden modificarse fácilmente para lograr un buen tiempo de ejecución en el mejor de los casos codificando soluciones para un conjunto finito de entradas, lo que hace que la medida sea prácticamente inútil. [ 2 ]

Rendimiento en el peor de los casos frente al rendimiento amortizado frente al rendimiento en el caso promedio.

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 suelen requerir 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 (consideremos, por ejemplo, los algoritmos diseñados para operar con cadenas de texto). De manera similar, incluso cuando es posible una descripción razonable de un "caso promedio" particular (que probablemente solo será aplicable para algunos usos del algoritmo), estas tienden a resultar en un análisis más difícil de las ecuaciones. [ 3 ]

El análisis del peor caso proporciona un análisis seguro (el peor caso nunca se subestima), pero que puede ser excesivamente pesimista , ya que puede que no exista ninguna entrada (realista) que requiera tantos pasos.

En ciertas situaciones, puede ser necesario recurrir a un análisis pesimista para garantizar la seguridad. Sin embargo, a menudo, un análisis pesimista puede resultar demasiado pesimista, por lo que un análisis más cercano al valor real, aunque optimista (quizás con una baja probabilidad de fallo conocida), puede ser un enfoque mucho más práctico. Un enfoque moderno en la teoría académica para salvar la brecha entre el análisis del peor caso y el del caso promedio se denomina análisis suavizado .

Al analizar algoritmos que suelen completarse en poco tiempo, 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 durante una serie (posiblemente infinita) de operaciones . Este coste amortizado puede ser mucho más cercano al coste medio, a la vez que proporciona un límite superior garantizado para el tiempo de ejecución. Por ejemplo, los algoritmos en línea suelen basarse en el análisis amortizado.

El análisis del peor caso está relacionado con la complejidad del peor caso . [ 4 ]

Consecuencias prácticas

Muchos algoritmos con un rendimiento deficiente en el peor de los casos presentan un buen rendimiento en el caso promedio. Para los problemas que queremos resolver, esto es positivo: podemos esperar que las instancias particulares que nos interesan sean promedio. En criptografía , esto es muy negativo: queremos que las instancias típicas de un problema criptográfico sean difíciles. En este caso, se pueden utilizar métodos como la autorreductibilidad aleatoria para algunos problemas específicos, demostrando 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, presentan un comportamiento muy deficiente en el peor de los casos, pero una tabla hash bien escrita y de tamaño suficiente nunca dará estadísticamente el peor caso; el número promedio de operaciones realizadas sigue una curva de decaimiento exponencial, por lo que el tiempo de ejecución de una operación está estadísticamente acotado.

Ejemplos

Algoritmos de ordenación

Gráficas de funciones comúnmente utilizadas en el análisis de algoritmos, que muestran el número de operaciones N en función del tamaño de entrada n para cada función.
  • El algoritmo de ordenación por inserción se aplica a una lista de n elementos, que se supone que son todos diferentes y están inicialmente en orden aleatorio. En promedio, la mitad de los elementos de una lista A 1 ... 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 va a insertar, en promedio, con la mitad de la sublista ya ordenada, de modo que t j = j /2. El cálculo del tiempo de ejecución promedio resultante produce una función cuadrática del tamaño de la entrada, al igual que el tiempo de ejecución en el peor de los casos.
  • El algoritmo Quicksort se aplica a una lista de n elementos, que se supone que son todos diferentes y están inicialmente en orden aleatorio. Este popular algoritmo de ordenación tiene un rendimiento promedio de O( n  log( n )), lo que contribuye a que sea un algoritmo muy rápido en la práctica. Sin embargo , ante 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 )). 
  • El algoritmo Heapsort tiene una complejidad temporal de O(n) cuando todos los elementos son iguales. Heapify requiere una complejidad temporal de O(n), y la eliminación de elementos del montón requiere una complejidad temporal de 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 algoritmo Bogosort tiene una complejidad temporal de O(n) cuando los elementos se ordenan en la primera iteración. En cada iteración, se comprueba si todos los elementos están ordenados. Existen n! permutaciones posibles; con un generador de números aleatorios balanceado, casi todas las permutaciones del arreglo se obtienen en n! iteraciones. Las computadoras tienen memoria limitada, por lo que los números generados entran en un bucle; es posible que no se pueda alcanzar cada permutación. En el peor de los casos, esto conlleva una complejidad temporal de O(∞), un bucle infinito.

Estructuras de datos

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

Véase también

Referencias

  1. ↑ "Complejidad en el mejor, peor y promedio caso - Complejidad y tratabilidad - Guía de campo de la informática" . www.csfieldguide.org.nz . Consultado el 23 de octubre de 2025 .
  2. ↑ Introducción a los algoritmos (Cormen, Leiserson, Rivest y Stein) 2001, Capítulo 2 "Primeros pasos". En la complejidad del mejor caso , proporciona el límite inferior del tiempo de ejecución del algoritmo para cualquier instancia de entrada.
  3. ↑ Spielman, Daniel ; Teng, Shang-Hua (2009), "Análisis suavizado: un intento de explicar el comportamiento de los algoritmos en la práctica" (PDF) , Communications of the ACM , 52 (10), ACM: 76–84 , doi : 10.1145/1562764.1562785 , S2CID 7904807 
  4. ↑ "Complejidad en el peor de los casos" (PDF) . Archivado (PDF) del original el 21/07/2011 . Consultado el 30/11/2008 .