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.