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
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.
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.
Cinco estrategias detrás de la mayoría de los 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.