Modelo por capas
Contar el trabajo que crece
Para comparar operaciones se cuenta el trabajo que crece con la cantidad de datos, n: comparaciones, copias, casilleros abiertos. Lo que no depende de n (preparar una variable, devolver un resultado) no cambia la comparación cuando n es grande.
Se escribe con la notación O, que dice cómo crece ese trabajo:
| Notación | Se lee | Con n = 1000 | Ejemplo |
|---|---|---|---|
| O(1) | constante | 1 | leer la posición i de un array |
| O(log n) | logarítmico | unas 10 | búsqueda binaria (descartar la mitad en cada paso; unidad 1) |
| O(n) | lineal | 1000 | recorrer todos los valores |
| O(n²) | cuadrático | 1 000 000 | comparar cada valor con todos los demás |
En la figura, la misma tabla como barras con n = 1000. La escala es logarítmica: cada marca multiplica por 10.
El primer programa del fenómeno compara cada correo con todos los demás: O(n²).