Hasta este punto hemos hablado de las notaciones mas sencillas:
- O(1)
- O(n)
- O(n²)
En ocasiones hay expresiones que requieren mas complejas como pueden llegar a ser las expresiones algorítmicas.
¿Qué son los logaritmos?
De la misma forma en que la división es lo inverso a la multiplicación, un logaritmo es el inverso a una potencia.
Por ejemplo para:
log(2,8)=3 => 2³ = 8
log(base, valor) = exponente => base^exponente = valor
El logaritmo de un número mide el número de veces que se tiene que dividir entre 2 hasta que se consiga un valor menor o igual a 1.
Por ejemplo el número 8, tiene que ser dividido 3 veces (2³).
8
4
2
1
log(8) = 3
El número 25 tiene que ser dividido 5 veces (2^5).
25
12.5
6.25
3.125
1.5625
0.78125
log(25) = 4.64
Complejidad del algoritmo
Lo que es realmente relevante es el comportamiento en la gráfica de una O(log n), como podemos ver el time complexity de O(log n) es apenas superior al time complexity de 0(1).
¿Por qué son importantes los logaritmos?
- Ciertos algoritmos de búsqueda tienen un time complexity tipo logarítmico.
- Algoritmos eficientes involucran el uso de logaritmos.
- La recursión implica en algunas ocasiones logaritmos para el space complexity.
