GUÍA DE ESTUDIO · UNOS 12 MIN DE LECTURA

Algoritmos

Un algoritmo es una receta precisa para resolver un problema. Uno bueno puede convertir cien pasos en siete. Elige un número secreto y mira cómo la búsqueda binaria lo encuentra partiendo el rango por la mitad cada vez.

BÚSQUEDA BINARIA · DEL 1 AL 100
1100
Rango 1-100. Primer intento: el centro.
Nunca más de 7 intentos para 100 números.

Qué es un algoritmo, en breve

Un algoritmo es una secuencia finita e inequívoca de pasos que convierte una entrada en una salida, como una lista en una lista ordenada o dos lugares en la ruta más corta entre ellos. Estudiar algoritmos significa diseñar esos pasos y medir cómo crece su coste a medida que crece la entrada.

La palabra viene de al-Juarismi, un matemático persa del siglo IX que trabajó en Bagdad y cuyo nombre, latinizado como Algoritmi, pasó a significar calcular con cifras indoarábigas.

Debe ser
Finito, preciso, efectivo, con entrada y salida claras
Se mide por
El tiempo y la memoria a medida que crece la entrada (O grande)
El más antiguo conocido
El método de Euclides para el MCD, c. 300 a. C.
No es lo mismo que
Un programa, que es una implementación suya
CONCEPTO CLAVE

La misma lista, tres formas de ordenarla

Ordenar es el problema clásico de los algoritmos. Elige un método y reprodúcelo. Fíjate en los contadores: distintas estrategias hacen cantidades de trabajo muy diferentes con los mismos diez números.

62941017385
Diez números sin ordenar. Pulsa reproducir o avanza un paso.
0comparaciones
0intercambios
Ordenación de burbujaCompara repetidamente los vecinos y los intercambia si están desordenados. Los números grandes suben como burbujas hasta el final.O(n²): sencillo pero lento
comparandoen su sitio definitivoen espera
NOTACIÓN O GRANDE

Por qué el crecimiento importa más que la velocidad

La O grande describe cómo crece el número de pasos con el tamaño de la entrada n. Sube n y mira cuánto tardaría cada tipo de algoritmo en un ordenador que hace mil millones de pasos por segundo.

O(1)acceso a un array1 ns
O(log n)búsqueda binaria6 ns
O(n)búsqueda lineal86 ns
O(n log n)ordenación por mezcla553 ns
O(n²)ordenación de burbuja7.4 µs
O(2ⁿ)subconjuntos por fuerza bruta10^9 años
Las barras usan una escala logarítmica; si no, todas menos la última serían invisibles. Los tiempos suponen exactamente n, n², etc. pasos a 10⁹ pasos por segundo.
PARADIGMAS DE DISEÑO

Cinco estrategias detrás de la mayoría de los algoritmos

ESTRATEGIALA IDEADÓNDE TE LA ENCUENTRAS
Divide y vencerásParte el problema en mitades, resuelve cada una y combina las respuestas.Ordenación por mezcla, búsqueda binaria, multiplicación rápida
VorazToma la opción que mejor pinta tiene en cada paso y nunca mira atrás. Rápido, pero no siempre óptimo.Dar el cambio con monedas, los caminos más cortos de Dijkstra
Programación dinámicaDivide un problema en subproblemas que se solapan y recuerda cada respuesta para calcularla una sola vez.Distancia de edición del corrector ortográfico, planificación de rutas, alineamiento de ADN
Búsqueda en grafosExplora las conexiones de forma sistemática, en anchura o en profundidad.Mapas, redes sociales, resolver laberintos y rompecabezas
Fuerza brutaPrueba todas las posibilidades. Funciona seguro, pero suele ser demasiado lento.Descifrar contraseñas cortas, rompecabezas pequeños, comprobar otros algoritmos

Más antiguos que los ordenadores

Los algoritmos se escribían en arcilla y papiro dos mil años antes de que nadie construyera una máquina para ejecutarlos.

c. 1600 a. C.Tablillas babilónicasProcedimientos paso a paso para la división y las raíces cuadradas, grabados en arcilla.
c. 300 a. C.El algoritmo de EuclidesHalla el máximo común divisor de dos números. Todavía se usa hoy en criptografía.
c. 820Al-KhwārizmīSus libros sobre la aritmética indoarábiga nos dieron la palabra «algoritmo».
1959QuicksortEl método de ordenación de Tony Hoare, todavía entre los más rápidos en la práctica.
1977RSAEl cifrado de clave pública de Rivest, Shamir y Adleman hizo posibles los pagos seguros por internet.
1998PageRankLarry Page y Sergey Brin ordenaron las páginas web según los enlaces que apuntaban a ellas.

Para leer más

Introduction to Algorithms· Cormen, Leiserson, Rivest & Stein1990
The Art of Computer Programming· Donald Knuth1968-
Grokking Algorithms· Aditya Bhargava2016
Algorithms to Live By· Brian Christian & Tom Griffiths2016

El pensamiento algorítmico es pensamiento lógico. Mide el tuyo.

Nuestro test de CI completo cubre el razonamiento lógico, numérico, verbal y espacial: 60 preguntas, unos 30 minutos.

Haz el test de CI completo