1.5 Análisis de Algoritmos
TecNM · ITSL¿Cuánto te cuesta
encontrar algo?
Imagina que pierdes las llaves en tu casa.
Ambas estrategias encuentran las llaves. La pregunta que nos interesa hoy no es si las encuentran, sino cuánto les cuesta encontrarlas.
¿Por qué nos importa
la eficiencia?
Un algoritmo lento no se nota con pocos datos. Con millones de datos, sí. Mueve el control y compruébalo tú mismo.
| Número de elementos | Búsqueda simple · O(n) | Búsqueda binaria · O(log n) |
|---|---|---|
| 10 | 10 ms | 3 ms |
| 100 | 100 ms | 7 ms |
| 10,000 | 10 seg | 14 ms |
| 1,000,000,000 | 11 días | 32 ms |
¿Cuánto creen que tarda buscar un dato entre 1,000 millones, revisando uno por uno?
en segundos,
medimos el tiempo
en pasos.
¿Qué es la
complejidad temporal?
Es el número de operaciones que realiza un algoritmo para completar su tarea (considerando que cada operación dura lo mismo).
"Menos pasos = más rápido", sin importar en qué computadora se ejecute.
Tres formas de
buscar una receta
Toca cada tarjeta para ver el ejemplo con datos reales
Sirves el platillo directo — sabes exactamente dónde está.
Ejemplo: arreglo[57] — sin importar si el arreglo tiene 10 o 10 millones de elementos, acceder a la posición 57 siempre cuesta 1 paso.
Revisas el recetario de principio a fin hasta encontrar la que buscas.
Con 100 recetas, en el peor caso revisas las 100. Con 10,000 recetas, hasta 10,000. El costo crece igual de rápido que los datos.
Abres por la mitad y descartas la mitad que no sirve, una y otra vez.
Con 10,000 recetas alfabetizadas, necesitas apenas ~14 comparaciones para encontrar cualquiera. Duplicar los datos solo suma 1 paso más.
¿Qué nos dice
realmente Big-O?
Nos dice cómo se va a comportar un algoritmo en función del tamaño de los datos — no cuántos segundos exactos tarda.
Ahora sí: la fórmula
Un trozo sencillo de programa:
S1;
for (int i = 0; i < N; i++)
S2;
Antes de irnos... repasemos