Muchos algoritmos para un mismo problema
Un algoritmo es un conjunto de pasos exactos para resolver un problema. La mayoría de los problemas se pueden resolver con más de un algoritmo. Por ejemplo, para encontrar un nombre en una lista puedes revisar todos los nombres o, si la lista está ordenada, ir partiéndola por la mitad.
Los dos dan la respuesta correcta. La diferencia es la eficiencia: cuánto trabajo y cuánta memoria necesita cada uno. Un buen programador elige el algoritmo que sigue siendo rápido cuando los datos se hacen grandes.
Comparar algoritmos por el tiempo que tardan
Medir con un cronómetro no es justo: un ordenador rápido hace que un algoritmo lento parezca bueno. Por eso contamos los pasos básicos (comparaciones, intercambios, sumas) en función del tamaño de la entrada n.
Mejor caso, caso promedio y peor caso
El mejor caso es la entrada con más suerte (el 13 está en la primera caja: 1 paso). El peor caso es la de menos suerte (el 13 no está: n pasos). Normalmente damos el peor caso, porque es una promesa: el algoritmo nunca será más lento que eso.
Complejidad temporal y complejidad espacial
La complejidad temporal dice cómo crece el número de pasos con n. La complejidad espacial dice cómo crece la memoria extra con n. El merge sort es rápido pero necesita memoria extra; el burbuja casi no necesita memoria extra pero es lento.
Notación Big O
Big O describe la rapidez de crecimiento, sin fijarse en detalles pequeños. Nos quedamos solo con el término más grande y quitamos los números constantes: 3n² + 5n + 2 pasa a ser O(n²), porque con n grande la parte n² es casi todo.
| Big O | Nombre | n = 16 | n = 1000 | Ejemplo |
|---|---|---|---|---|
| O(1) | constante | 1 | 1 | leer el elemento 5 de un arreglo |
| O(log n) | logarítmica | 4 | unos 10 | búsqueda binaria |
| O(n) | lineal | 16 | 1000 | búsqueda lineal, hallar el mayor |
| O(n log n) | n log n | 64 | unos 10,000 | merge sort |
| O(n²) | cuadrática | 256 | 1,000,000 | ordenamiento burbuja, bucles anidados |
Regla rápida para el código: un bucle sobre n elementos es O(n); un bucle dentro de otro bucle es O(n²); partir el problema por la mitad cada vez es O(log n).
Eficiencia de la búsqueda lineal y la binaria
La búsqueda lineal revisa los elementos uno por uno. Peor caso: n comparaciones, es decir, O(n). Funciona con cualquier lista, ordenada o no.
La búsqueda binaria necesita una lista ordenada. Mira el elemento del medio; si es demasiado grande, descarta la mitad derecha; si no, la izquierda. Cada paso parte la lista por la mitad, así que el peor caso es de unas log₂ n + 1 comparaciones: O(log n). Con 1,000,000 de elementos son unos 20 pasos en vez de 1,000,000.
Eficiencia de los algoritmos de ordenamiento
Los ordenamientos burbuja, por inserción y por selección usan un bucle dentro de otro, así que hacen unas n²/2 comparaciones: O(n²). El ordenamiento por inserción es O(n) en el mejor caso (una lista que ya está ordenada).
El merge sort parte la lista por la mitad unas log₂ n veces y hace un trabajo de unos n en cada nivel: O(n log n). Necesita O(n) de memoria extra.
La búsqueda binaria necesita una lista ordenada. Si buscas una sola vez, ordenar primero (n log n) cuesta más que una búsqueda lineal (n). Si buscas muchas veces, ordenar una vez compensa.
Precondiciones, postcondiciones y errores típicos de la recursión
Una precondición es lo que debe cumplirse antes de que empiece el algoritmo (búsqueda binaria: la lista está ordenada). Una postcondición es lo que se garantiza al terminar (ordenar: cada elemento es menor o igual que el siguiente). Escribirlas ayuda a probar y demostrar un algoritmo.
Recursión significa que una función se llama a sí misma con un problema más pequeño. Errores comunes:
- No tener caso base, o tener uno que nunca se alcanza: las llamadas no paran nunca (desbordamiento de pila).
- El problema no se hace más pequeño en cada llamada.
- Repetir el mismo trabajo: un Fibonacci recursivo simple llama a fib(3) una y otra vez, así que crece como O(2ⁿ). Guardar las respuestas (memoización) lo deja en O(n).
- Una recursión muy profunda gasta mucha memoria, un marco de pila por cada llamada.
Pruébalo: una carrera entre dos búsquedas
Escribe los números del 1 al 32 en papelitos y ponlos en orden boca abajo. Pide a un amigo que elija un número secreto. Primero busca de uno en uno y cuenta los papelitos que das la vuelta. Luego busca dando siempre la vuelta al papelito del medio. Repite 5 veces. ¿Qué método nunca necesitó más de 6 vueltas? Compruébalo con el control del último paso 3D (n = 32: log₂ 32 = 5).
Fórmulas y definiciones clave
- Búsqueda lineal: peor caso n comparaciones → O(n)
- Búsqueda binaria: peor caso unas log₂ n + 1 comparaciones → O(log n)
- Ordenamiento burbuja / inserción / selección: unas n(n − 1)/2 comparaciones → O(n²)
- Merge sort: unas n log₂ n comparaciones → O(n log n)
- Regla de Big O: quédate con el término mayor y quita las constantes (5n² + 3n → O(n²))
- Al duplicar n: O(1) igual, O(log n) +1, O(n) ×2, O(n²) ×4
Ejemplos resueltos
1. Una lista tiene 50 nombres. ¿Cuántas comparaciones necesita la búsqueda lineal en el mejor y en el peor caso?
Mejor caso: el nombre es el primero → 1 comparación. Peor caso: el nombre es el último o no está → 50 comparaciones. La búsqueda lineal es O(n).
2. ¿Cuál es el máximo de comparaciones que necesita la búsqueda binaria en una lista ordenada de 1024 elementos?
Cada paso parte la lista por la mitad: 1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1. Son 10 divisiones, más la última comprobación: como máximo 11 comparaciones (log₂ 1024 = 10).
3. Da el Big O de f(n) = 4n² + 10n + 7.
Quédate con el término mayor (4n²) y quita la constante 4: O(n²).
4. Un bucle recorre i de 1 a n y, dentro, otro bucle recorre j de 1 a n. ¿Cuántas veces se ejecuta la línea interna?
n veces por cada uno de los n valores de i: n × n = n². Complejidad temporal O(n²).
5. Un programa O(n²) ordena 1000 elementos en 2 segundos. ¿Cuánto tardará aproximadamente con 3000 elementos?
n se hace 3 veces mayor, así que n² se hace 3² = 9 veces mayor: unos 2 × 9 = 18 segundos.
6. Compara el ordenamiento burbuja y el merge sort con n = 1000 elementos.
Burbuja: unas n²/2 = 500,000 comparaciones. Merge sort: unas n log₂ n = 1000 × 10 = 10,000. El merge sort hace unas 50 veces menos trabajo, pero necesita memoria extra.
Errores comunes
- Medir la rapidez solo con un cronómetro en un ordenador. Mejor cuenta los pasos en función de n.
- Usar la búsqueda binaria en una lista sin ordenar. Su precondición es que la lista esté ordenada.
- Dejar constantes en Big O, como escribir O(2n). Es simplemente O(n).
- Escribir una función recursiva sin caso base, o que no hace más pequeño el problema.