> ## Documentation Index > Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt > Use this file to discover all available pages before exploring further. # Mejor, peor y caso medio: análisis experimental de algoritmos > Cómo analizar el coste de un algoritmo: talla de la entrada, operación crítica, mejor caso, peor caso y caso medio, notación O y análisis experimental con gráficas y tablas, con ejemplos en C. Cuenta operaciones en el mejor, el peor y el caso medio para cada talla, con gráfica y tabla. ¿Cuánto tarda un algoritmo? Depende del ordenador, del lenguaje y, sobre todo, de **los datos**: del tamaño de la entrada y, a veces, de cómo estén colocados. Para comparar algoritmos de forma justa se cuenta cuántas veces se ejecuta la **operación crítica** y se estudia cómo crece con la talla, en el **mejor**, el **peor** y el **caso medio**. ## Lo que vas a aprender * Qué son la talla de la entrada y la operación crítica. * Distinguir mejor caso, peor caso y caso medio. * Expresar el coste con la notación O. * Comprobar experimentalmente el orden de un algoritmo. ## Cómo se usa el simulador * Elige el algoritmo: **búsqueda lineal**, **matriz por vector**, **inserción** o **búsqueda binaria**. * Elige la **talla máxima** (100 – 1000). * La gráfica dibuja las operaciones según la talla en el **mejor**, **medio** y **peor** caso. * La tabla da los resultados para cada talla y una columna que divide el peor caso entre la función teórica: si se estabiliza en una constante, se confirma el orden. * Se muestra el **código en C** con la operación que se cuenta, qué entrada da cada caso y cómo se mide el tiempo con `clock()`. ## Fundamentos teóricos ### Talla y operación crítica * **Talla** ($n$): el tamaño de la entrada (elementos de un vector, filas de una matriz…). * **Operación crítica**: la que más veces se ejecuta. Contarla es proporcional al tiempo y no depende del ordenador. ### Los tres casos * **Mejor caso**: la entrada de talla $n$ que **menos** trabajo da. * **Peor caso**: la que **más** trabajo da. Es una **garantía**: nunca tardará más. * **Caso medio**: lo que cuesta **de media** con entradas al azar. Si el trabajo solo depende de $n$ (sumar un vector, multiplicar matrices), los tres casos coinciden. ### Notación O $f(n) = O(g(n))$ significa que, para $n$ grande, $f$ crece como mucho como $g$ (salvo constantes). Órdenes típicos, de menor a mayor: $$ O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) $$ ### Algoritmos del simulador | Algoritmo | Mejor | Peor | Medio | | - | - | - | - | | Búsqueda lineal | $O(1)$ (está el primero) | $O(n)$ (no está) | $O(n)$ | | Matriz × vector | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | | Ordenación por inserción | $O(n)$ (ya ordenado) | $O(n^2)$ (al revés) | $O(n^2)$ | | Búsqueda binaria | $O(1)$ (está en el centro) | $O(\log n)$ | $O(\log n)$ | ### Análisis experimental 1. Elegir varias tallas. 2. Para cada una, generar entradas del caso que se estudia y contar operaciones (o medir tiempo). 3. Dibujar la gráfica talla–operaciones. 4. Dividir entre la función teórica: si el cociente tiende a una constante, se confirma. Al medir tiempos reales con `clock()`, se repite la ejecución muchas veces y se divide, porque con tallas pequeñas una sola ejecución dura menos que la resolución del reloj. ## Ejemplos resueltos En un vector de 1000 elementos: mejor caso 1 comparación (está en `V[0]`); peor caso unas 1000 (no está); caso medio unas 500. Con 100 elementos ya ordenados: 99 comparaciones. Al revés: $100 \cdot 99/2 = 4950$. Con 1000 elementos, el peor caso es de unas 10 comparaciones; con un millón, unas 20. ## Experimenta con el simulador Mira la columna "peor / n" de la búsqueda lineal. ¿Se estabiliza? Compara las tres curvas de la inserción. ¿Por qué el mejor caso es una recta? Con la búsqueda binaria, duplica la talla máxima. ¿Cuánto crece el peor caso? ## Errores frecuentes * **Decir que el mejor caso es $n = 1$.** Los casos se comparan **a igual talla**. * **Confundir caso medio con la media entre mejor y peor.** * **Quedarse con las constantes** al dar el orden: $3n + 5$ es $O(n)$. ## Herramientas relacionadas Mejor y peor caso de cada algoritmo. Ecuaciones de recurrencia. Ajustar datos experimentales. This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.