Tema 5
Logaritmos
Patrón de examen
Cada vez que un algoritmo divide el problema a la mitad, su complejidad incluye log(n). Usa log₂ para estimar si una solución O(n log n) cabe en el tiempo.
Explicación
¿Qué es un logaritmo?
El logaritmo responde: ¿a qué potencia debo elevar la base para obtener el número?
$$\log_b(x) = y \iff b^y = x$$
Ejemplos clave
| Expresión | Valor | Por qué |
|---|---|---|
| log₂(8) | 3 | 2³ = 8 |
| log₂(1024) | 10 | 2¹⁰ = 1024 |
| log₁₀(1000) | 3 | 10³ = 1000 |
| log₂(1) | 0 | 2⁰ = 1 |
Propiedades fundamentales
log(a × b) = log(a) + log(b)log(a / b) = log(a) - log(b)log(aⁿ) = n × log(a)log_b(a) = log(a) / log(b)— cambio de base
¿Por qué importan en programación?
El logaritmo base 2 aparece en toda estructura que divide el problema a la mitad:
| Algoritmo/estructura | Complejidad | Razón |
|---|---|---|
| Búsqueda binaria | O(log n) | Divide a la mitad en cada paso |
| Merge sort | O(n log n) | log n niveles de recursión |
| Árbol binario balanceado | O(log n) | Altura = log₂(n) |
| Segment Tree | O(log n) | Igual, árbol binario |
Tabla rápida de log₂
| n | log₂(n) |
|---|---|
| 10³ | ~10 |
| 10⁶ | ~20 |
| 10⁹ | ~30 |
| 10¹⁸ | ~60 |
Esto explica por qué O(log n) es tan rápido: incluso con n = 10⁹, son solo ~30 operaciones.