Que es un algoritmo?
Un algoritmo es un conjunto de instrucciones que realizan una tarea. Puede ser una receta de cocina, un manual de montaje o, en nuestro caso, un procedimiento que una computadora sigue para resolver un problema.
La diferencia entre un algoritmo bueno y uno malo puede ser la diferencia entre resolver algo en 30 operaciones o en 1.000 millones. Es exactamente de eso de lo que vamos a hablar.
Busqueda Binaria
Imagina que estas buscando un nombre en una guia telefonica con 128 nombres ordenados alfabeticamente. El enfoque mas ingenuo seria mirar nombre por nombre, de principio a fin. En el peor caso, harias 128 verificaciones.
La busqueda binaria funciona de forma mucho mas inteligente: abres la guia por la mitad, verificas si el nombre que buscas viene antes o despues, y descartas la mitad de los elementos de una sola vez. Luego repites el proceso con la mitad restante.
Con 128 nombres, el maximo de pasos es 7 (porque log2 128 = 7). Si la lista tiene 256 nombres, son solo 8 pasos. Duplicamos la entrada y agregamos solo un unico paso mas.
Requisito fundamental
La busqueda binaria solo funciona con listas ordenadas. Si la lista no esta en orden, necesitas ordenarla primero o usar otro metodo de busqueda.
Implementacion en Python
def busqueda_binaria(lista, objetivo):
bajo = 0
alto = len(lista) - 1
while bajo <= alto:
medio = (bajo + alto) // 2
intento = lista[medio]
if intento == objetivo:
return medio
if intento > objetivo:
alto = medio - 1
else:
bajo = medio + 1
return None # no encontrado
# Ejemplo de uso
mi_lista = [1, 3, 5, 7, 9, 11, 13, 15]
print(busqueda_binaria(mi_lista, 7)) # 3 (indice del elemento)
print(busqueda_binaria(mi_lista, 10)) # NoneEn cada iteracion, el espacio de busqueda se divide a la mitad. Esto resulta en una complejidad de O(log n).
Logaritmos
Si la exponenciacion es multiplicar una base por si misma varias veces, el logaritmo es la operacion inversa: responde “cuantas veces necesito multiplicar la base para llegar a este numero?”.
- log10 100 = 2 — necesito multiplicar 10 por si mismo 2 veces para llegar a 100 (10 x 10 = 100)
- log2 128 = 7 — necesito multiplicar 2 por si mismo 7 veces para llegar a 128
- log2 256 = 8 — uno mas que 128, porque duplicamos el numero
En ciencias de la computacion, cuando decimos O(log n), generalmente nos referimos a log en base 2. Por eso la busqueda binaria es tan eficiente: cada paso elimina la mitad del problema.
Notacion Big O
La notacion Big O describe como escala un algoritmo conforme el tamano de la entrada crece. No mide el tiempo en segundos, sino el numero de operaciones en el peor caso.
Comparacion practica
Considera una lista con 1.000 millones de elementos (10^9):
| Algoritmo | Operaciones |
|---|---|
| Busqueda simple O(n) | 1.000.000.000 |
| Busqueda binaria O(log n) | ~30 |
La diferencia es absurda. Mientras la busqueda simple necesita verificar cada elemento, la busqueda binaria resuelve el problema en unos 30 pasos.
Complejidades mas comunes
| Notacion | Nombre | Ejemplo |
|---|---|---|
| O(1) | Constante | Acceder a un elemento de array por indice |
| O(log n) | Logaritmica | Busqueda binaria |
| O(n) | Lineal | Busqueda simple (recorrer toda la lista) |
| O(n log n) | Linearitmica | Quicksort, Merge sort |
| O(n^2) | Cuadratica | Selection sort, bucles anidados |
| O(n!) | Factorial | Viajante de comercio (fuerza bruta) |
Que significa en la practica?
Para tener una nocion concreta, observa cuantas operaciones requiere cada complejidad para diferentes tamanos de entrada:
| n | O(1) | O(log n) | O(n) | O(n log n) | O(n^2) | O(n!) |
|---|---|---|---|---|---|---|
| 10 | 1 | ~3 | 10 | ~33 | 100 | 3.628.800 |
| 100 | 1 | ~7 | 100 | ~664 | 10.000 | imposible |
| 1.000 | 1 | ~10 | 1.000 | ~9.966 | 1.000.000 | imposible |
La complejidad O(n!) es particularmente aterradora: para n = 20, estamos hablando de aproximadamente 2,4 trillones de operaciones. Por eso problemas como el del viajante de comercio no tienen solucion exacta eficiente para entradas grandes.
Arrays vs Listas Enlazadas
Antes de hablar de Quicksort, vale la pena entender dos estructuras de datos fundamentales.
Arrays
- Almacenan elementos en posiciones secuenciales en memoria
- Lectura por indice es instantanea: O(1)
- Insercion es problematica: si no hay espacio contiguo disponible, todos los elementos necesitan ser movidos — O(n)
- Tamano generalmente fijo (o necesita reasignacion)
Listas enlazadas
- Cada elemento guarda una referencia (puntero) al siguiente
- Los elementos pueden estar dispersos en la memoria
- Insercion es rapida: basta con actualizar los punteros — O(1)
- Lectura por posicion requiere recorrer la lista desde el inicio — O(n)
Resumen comparativo
| Operacion | Array | Lista enlazada |
|---|---|---|
| Lectura | O(1) | O(n) |
| Insercion | O(n) | O(1) |
| Eliminacion | O(n) | O(1) |
Cuando usar cada uno?
- Arrays: cuando necesitas acceder a elementos por indice con frecuencia (ej.: tabla de precios, ranking)
- Listas enlazadas: cuando las inserciones y eliminaciones son frecuentes y la lectura secuencial es aceptable (ej.: cola de tareas, playlist)
En la practica, la mayoria de los lenguajes modernos ofrecen estructuras hibridas (como ArrayList en Java o list en Python) que combinan lo mejor de ambos mundos.
Quicksort
El Quicksort es uno de los algoritmos de ordenamiento mas usados en la practica. Utiliza la tecnica Divide y Venceras (Divide and Conquer), que consiste en:
- Definir un caso base (generalmente un array vacio o con un unico elemento, que ya esta ordenado)
- Reducir el problema hasta llegar al caso base
Divide y Venceras
La tecnica DC (Divide and Conquer) es una estrategia general para resolver problemas:
- Divide el problema en subproblemas mas pequenos
- Conquista cada subproblema recursivamente
- Combina los resultados
La busqueda binaria tambien usa esta logica: divide el espacio de busqueda a la mitad en cada paso. El Quicksort aplica el mismo principio para el ordenamiento.
Como funciona
- Elige un elemento como pivote (pivot)
- Particiona el array en dos sub-arrays: elementos menores que el pivote y elementos mayores que el pivote
- Aplica el Quicksort recursivamente en cada sub-array
- Combina los resultados
Implementacion en Python
def quicksort(lista):
if len(lista) < 2:
return lista # caso base: lista vacia o con 1 elemento
pivote = lista[0]
menores = [i for i in lista[1:] if i <= pivote]
mayores = [i for i in lista[1:] if i > pivote]
return quicksort(menores) + [pivote] + quicksort(mayores)
# Ejemplo de uso
print(quicksort([10, 5, 2, 3])) # [2, 3, 5, 10]
print(quicksort([33, 15, 10, 7])) # [7, 10, 15, 33]Seleccion del pivote
La eleccion del pivote impacta directamente en el rendimiento:
- Pivote fijo (primer elemento): simple pero peligroso. Si el array ya esta ordenado, el Quicksort degenera a O(n^2)
- Pivote aleatorio: estrategia recomendada. Al elegir aleatoriamente, la probabilidad de caer en el peor caso es muy baja
- Mediana de tres: elige la mediana entre el primer, el medio y el ultimo elemento. Una buena heuristica
Complejidad
| Caso | Complejidad | Cuando ocurre |
|---|---|---|
| Mejor caso | O(n log n) | El pivote divide el array a la mitad |
| Caso promedio | O(n log n) | Pivote aleatorio, divisiones razonables |
| Peor caso | O(n^2) | El pivote es siempre el menor o el mayor elemento |
En la practica, el caso promedio es el mas comun, y el Quicksort tiende a ser mas rapido que otros algoritmos O(n log n) como el Merge Sort, por tener constantes menores y mejor uso de cache.
Conclusion
Estos conceptos forman la base para entender la eficiencia de cualquier software:
- Busqueda binaria transforma busquedas de miles de millones de operaciones en decenas
- Big O nos da un lenguaje comun para comparar algoritmos
- Arrays y listas enlazadas tienen trade-offs claros que impactan el rendimiento
- Quicksort muestra como la tecnica Divide y Venceras resuelve problemas de ordenamiento de forma elegante
Entender algoritmos no es solo un ejercicio academico. Es lo que separa un sistema que soporta escala de uno que colapsa con mil usuarios.