Logaritmos

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 algoritmo 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).

Big O

¿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.

VPN

  • Ir a la oferta de NordVPN

Moda

Accesorios