Funcionaba bien con cien clientes
Una empresa de reparto prueba un programa con 100 clientes y responde al momento.
Un año después tiene 100 000 clientes. El mismo programa tarda veinte minutos en cada informe.
El código no ha cambiado. Lo que ha cambiado es la cantidad de datos. Saber cómo crece el trabajo con los datos es lo que separa un programa que aguanta de uno que no.
Al final de esta lección
Nota
Puedo comparar cómo crecen dos algoritmos cuando hay más datos.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Paso | una operación sencilla, como comparar dos valores | |
| Crecimiento | cómo aumentan los pasos al aumentar los datos | |
| Lineal | el doble de datos, el doble de pasos | |
| Cuadrático | el doble de datos, cuatro veces más pasos | |
| Notación O grande | una forma corta de nombrar el crecimiento | O(n) |
| Árbol | datos colgados unos de otros, como un organigrama | |
| Grafo | puntos unidos por conexiones, como un mapa de rutas |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Se cuentan pasos, no segundos
Los segundos dependen del ordenador. Los pasos, no. Por eso se comparan algoritmos contando pasos.
Un algoritmo que mira cada dato una vez hace tantos pasos como datos hay. Su crecimiento es lineal.
Uno que compara cada dato con todos los demás hace muchos más. Con 10 datos hace 100 pasos. Su crecimiento es cuadrático.
Prueba: contar los pasos
# Dos formas de revisar una lista de n pedidos.
def steps_one_pass(n):
# Mirar cada pedido una vez: por ejemplo, sumar importes.
steps = 0
for i in range(n):
steps = steps + 1
return steps
def steps_every_pair(n):
# Comparar cada pedido con todos los demás: buscar duplicados así.
steps = 0
for i in range(n):
for j in range(n):
steps = steps + 1
return steps
for n in [10, 100, 1000]:
print(n, "pedidos | una pasada:", steps_one_pass(n), "| todos los pares:", steps_every_pair(n))
# Añade 2000 a la lista de tamaños. ¿Cuántas veces crece cada columna?
Cada crecimiento tiene un nombre
Los equipos técnicos usan la notación O grande para decir cómo crece un algoritmo. La letra n es la cantidad de datos.
O(1) es constante: siempre los mismos pasos, como leer un diccionario. O(log n) divide entre dos en cada paso, como la búsqueda binaria. O(n) es lineal, como la búsqueda lineal. O(n²) es cuadrático, como la ordenación por selección.
En una entrevista te pedirán decir cuál es cada uno.
Ejemplo resuelto: pasos según la cantidad de datos
| Crecimiento | Ejemplo del módulo | 10 datos | 1000 datos | 1 000 000 datos |
|---|---|---|---|---|
| O(1), constante | Leer un diccionario | 1 | 1 | 1 |
| O(log n), divide entre dos | Búsqueda binaria | 4 | 10 | 20 |
| O(n), lineal | Búsqueda lineal | 10 | 1000 | 1 000 000 |
| O(n²), cuadrático | Ordenación por selección | 100 | 1 000 000 | un billón |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Un error frecuente
Advertencia
Mucha gente cree que un ordenador más rápido arregla un algoritmo lento. Solo ayuda un poco. Con un millón de datos, un algoritmo cuadrático hace un billón de pasos, un millón de millones. Ningún servidor compensa eso. Cambiar a un algoritmo lineal, sí.
Árboles y grafos: lo que viene después
Las listas, las pilas, las colas y los diccionarios cubren buena parte del trabajo diario. Hay dos estructuras más que verás pronto.
Un árbol cuelga unos datos de otros, como el organigrama de una empresa o las carpetas de un disco. Un grafo une puntos con conexiones, como las rutas de una empresa de reparto o una red de ordenadores.
Quedan para un módulo posterior.