Big O – Ejemplo de código O(log(n))

Si encuentras algo que no entiendes puedes comentarlo y haremos todo lo posible de ayudarte lo mas rápido que podamos.

Solución:

Ejemplo clásico:

while (x > 0)   
   x /= 2;  
  

Esto será:

Iteration |   x
----------+-------
    0     |   x
    1     |  x/2
    2     |  x/4
   ...    |  ...
   ...    |  ...
    k     |  x/2^k 

2^k = x → Aplicando log a ambos lados → k = log(x)

Por definición, log(n) (quiero decir aquí log con base 2, pero la base realmente no importa), es el número de veces que tienes que multiplicar 2 por sí mismo para obtener n. Entonces, el ejemplo de código O(log(n)) es:

i = 1
while(i < n)
    i = i * 2
    // maybe doing addition O(1) code

En ejemplos de código reales, puede encontrar O(log(n)) en búsqueda binaria, árboles de búsqueda binarios balanceados, muchos algoritmos recursivos, colas de prioridad.

Para O (inicio de sesión), eche un vistazo a cualquier código que involucre la estrategia de dividir y vencer

Calificaciones y reseñas

Si piensas que ha sido de ayuda nuestro artículo, sería de mucha ayuda si lo compartes con otros entusiastas de la programación de esta forma nos ayudas a extender este contenido.

---

---

Utiliza Nuestro Buscador