Casos peor, mejor y promedio

En análisis de algoritmos, los términos caso peor, caso mejor y caso promedio tienen los siguientes significados:

Caso mejor: se refiere a la situación inicial de los datos que genera una ejecución del algoritmo con una menor complejidad computacional.
Caso peor: se refiere a la situación inicial de los datos que genera una ejecución del algoritmo con una complejidad computacional mayor.^[1]
Caso promedio: la situación inicial de los datos no sigue ningún patrón preestablecido que aporte ventajas o desventajas. Se puede considerar, por tanto, la situación típica de ejecución del algoritmo.^[2]

En el caso de los algoritmos de ordenamiento o clasificación, la complejidad computacional está determinada por el número de comparaciones y de asignaciones entre elementos del conjunto que se realiza en una implementación específica del algoritmo.

Por ejemplo, en el algoritmo de Inserción directa el caso mejor se presenta cuando el conjunto de elementos a ordenar se encuentra ya ordenado. En ese caso, los valores representativos son los siguientes:

$C_{min}=n-1$

$M_{min}=2(n-1)$

donde $C_{min}$ y $M_{min}$ son el número mínimo de comparaciones y el número mínimo de movimientos entre elementos del conjunto de datos del algoritmo de Inserción directa.

Referencias

↑ Ye, Yinyu (1997). «Worst-Case Analysis». En John Wiley & Sons, Inc., ed. Interior Point Algorithms. ISBN 9781118032701.
↑ Scott Vitter, Jeffrey; Flajolet, Philippe (1990). «Average-Case Analysis of Algorithms and Data Structures». En North-Holland, ed. Handbook of Theoretical Computer Science).

Datos: Q186094

[1] Ye, Yinyu (1997). «Worst-Case Analysis». En John Wiley & Sons, Inc., ed. Interior Point Algorithms. ISBN 9781118032701.

[2] Scott Vitter, Jeffrey; Flajolet, Philippe (1990). «Average-Case Analysis of Algorithms and Data Structures». En North-Holland, ed. Handbook of Theoretical Computer Science).

[1]

[2]