Tema 1
Complejidad de algoritmos
Patrón de examen
Antes de implementar, calcula la complejidad de tu solución con los límites del problema. Si supera 10⁸ operaciones, busca un algoritmo mejor.
Explicación
Notación Big-O
Mide cómo crece el tiempo de ejecución en función del tamaño de la entrada n.
| Complejidad | Nombre | n=10⁶ factible? |
|---|---|---|
| O(1) | Constante | ✓ |
| O(log n) | Logarítmica | ✓ |
| O(n) | Lineal | ✓ |
| O(n log n) | Lineal-logarítmica | ✓ |
| O(n²) | Cuadrática | Solo si n ≤ 10⁴ |
| O(2ⁿ) | Exponencial | Solo si n ≤ 25 |
Regla práctica de olimpiadas
Una computadora ejecuta aproximadamente 10⁸ operaciones por segundo.
- n ≤ 10⁶ → O(n) o O(n log n)
- n ≤ 10⁴ → O(n²) tolerable
- n ≤ 500 → O(n³) tolerable
Análisis de ciclos
for i = 1..n → O(n)
for j = 1..n → O(n²)
for k = 1..n → O(n³)
for i = 1..n → O(n log n)
for j = i; j > 0; j/=2
while n > 1: n /= 2 → O(log n)