Mejor y peor caso
Ejecuta cada algoritmo con entradas de distintas tallas y compara cuántas operaciones hace en el mejor caso, en el peor y de media.
| Talla n | Mejor | Medio | Peor | Peor / n |
|---|---|---|---|---|
| 50 | 1 | 26,6 | 51 | 1,020 |
| 100 | 1 | 54,7 | 101 | 1,010 |
| 150 | 1 | 71,5 | 151 | 1,007 |
| 200 | 1 | 90 | 201 | 1,005 |
| 250 | 1 | 137,7 | 251 | 1,004 |
| 300 | 1 | 136,5 | 301 | 1,003 |
| 350 | 1 | 204,9 | 351 | 1,003 |
| 400 | 1 | 243,5 | 401 | 1,002 |
| 450 | 1 | 183,5 | 451 | 1,002 |
| 500 | 1 | 258,2 | 501 | 1,002 |
Si la última columna se estabiliza en una constante, el peor caso crece como n. El caso medio es la media de 20 entradas al azar.
1int busqueda_lineal(int V[], int n, int x)2{3 int i = 0;4 while (i < n && V[i] != x) // se cuenta5 i++;6 return i < n ? i : -1;7}La línea resaltada es la operación que se cuenta: la que más veces se ejecuta.
| Mejor | x está en V[0] | 1 |
| Medio | x en una posición al azar | 258,2 |
| Peor | x no está en el vector | 501 |
Operaciones con n = 500.
1#define NUM_TALLAS 102int tallas[NUM_TALLAS] = {100, 200, ..., 1000};3int repite[NUM_TALLAS] = {10000, ..., 1000};4 5for (i = 0; i < NUM_TALLAS; i++) {6 n = tallas[i];7 V = crea_vector(n);8 rellena_peor_caso(V, n); // o el mejor9 t0 = clock();10 for (r = 0; r < repite[i]; r++) // repetir para11 algoritmo(V, n); // medir algo12 t1 = clock();13 t = (t1 - t0) / (double) CLOCKS_PER_SEC / repite[i];14 printf("%d\t%f\n", n, t);15 free(V);16}En las prácticas se mide el tiempo con clock(): se prepara una entrada de cada talla con el caso que se quiere estudiar, se ejecuta el algoritmo muchas veces y se divide entre el número de repeticiones, porque una sola ejecución es más corta que la resolución del reloj.
Aquí contamos cuántas veces se ejecuta la operación crítica en lugar de medir segundos: el tiempo es proporcional a ese número y así el resultado no depende del ordenador ni del ruido del navegador.
Con los tiempos en una hoja de cálculo, dibuja la gráfica talla–tiempo y ajusta una línea de tendencia del tipo que predice la teoría (lineal, cuadrática, logarítmica).
El tiempo de un algoritmo depende de la talla de la entrada, n, pero a veces también de cómo sean los datos. El mejor caso es la entrada de talla n que menos trabajo da, el peor caso la que más, y el caso medio lo que cuesta de media con datos al azar.
El análisis experimental consiste en ejecutar el algoritmo con entradas de distintas tallas, medir y dibujar la gráfica talla–tiempo. Aquí se cuenta cuántas veces se ejecuta la operación crítica, que es proporcional al tiempo y no depende del ordenador.
Elige un algoritmo y mira las tres curvas. La última columna de la tabla divide el peor caso entre la función que predice la teoría: si se estabiliza en una constante, el experimento confirma el orden de complejidad.
¿Cuántas comparaciones hace la búsqueda lineal en un vector de 1000 elementos?
- Mejor caso: x está en V[0]. Una sola comparación.
- Peor caso: x no está. Se recorre todo el vector: unas 1000 comparaciones.
- Caso medio: si x está en una posición al azar, se recorre de media la mitad: unas 500.
Mejor O(1), peor O(n) y medio O(n)
Preguntas frecuentes
¿Todos los algoritmos tienen mejor y peor caso?
No. Si el trabajo solo depende de n, como sumar un vector o multiplicar matrices, todas las entradas de la misma talla cuestan lo mismo y se habla solo de O(f(n)).
¿Por qué se repite la ejecución muchas veces al medir con clock()?
Porque con tallas pequeñas una ejecución dura menos que la resolución del reloj y saldría 0. Se ejecuta muchas veces y se divide el tiempo total entre las repeticiones.
¿Qué caso se usa para dar la complejidad de un algoritmo?
Normalmente el peor, porque es una garantía: nunca tardará más. El caso medio es útil cuando el peor es raro, como en quicksort.
¿Por qué la inserción es O(n) en el mejor caso?
Con el vector ya ordenado, cada elemento se compara una vez con el anterior y se queda donde está: n − 1 comparaciones en total. Con el vector al revés, cada elemento recorre todo lo anterior: unas n²/2.