O(log n)

JavaScript · Unidad 21: Complejidad

Hay algo mejor que mirar todo: tirar la mitad en cada paso.

Partir 8 a la mitad hasta llegar a 1 toma 3 pasos; partir 1024, apenas 10. Eso es O(log n).

function mitades(n) {
  let p = 0;
  while (n > 1) {
    n = Math.floor(n / 2);
    p++;
  }
  return p;
}
console.log(mitades(8), mitades(1024));

Imprime

3 10

El resto de la explicación está en la lección, que es del plan completo.

Ejercicios de esta lección

Se hacen en la app, que los corrige al momento y explica por qué.

1. Predice la salida
El segundo número es el doble del primero. ¿Qué imprime?
2. Ordena las líneas
Cuenta cuántas veces se parte 64 a la mitad hasta llegar a 1.
3. Completa el código
Completa para que el contador cuente las mitades de 100.
4. Opción múltiple
Tienes 1000 nombres ordenados de la A a la Z. Si en cada intento descartas la mitad, ¿cuántos nombres miras en el peor caso?
5. Encuentra el bug
pasosHasta(n) debe contar cuántas veces hay que duplicar el 1 para llegar a n. Con 1000 debe dar 10. ¿Qué línea tiene el error?
6. Encuentra el caso que falla
mitades(n) debe decir cuántas veces se puede partir n a la mitad, quedándose siempre con la parte entera, hasta llegar a 1. mitades(1) es 0. ¿Con cuál llamada falla?
7. Predice la salida
El ciclo de adentro parte m a la mitad. ¿Qué imprime?
8. Predice la salida
Este hace primero un trabajo de mitades y luego un recorrido completo. ¿Qué imprime?

Se abre en el navegador. Esta lección es del plan completo; la primera unidad de cada curso es gratis.