O(log n)

Python · Unidad 22: Complejidad

Hay un ritmo mucho más barato que O(n): tirar la mitad de lo que queda en cada paso.

De 1024 a 1, partiendo a la mitad, son solo 10 pasos. Esa etiqueta es O(log n).

n = 1024
pasos = 0
while n > 1:
    n = n // 2
    pasos += 1
print(pasos)

Imprime

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
¿Qué imprime este código?
2. Predice la salida
¿Qué imprime este código?
3. Opción múltiple
Tienes una lista ordenada con un millón de números y en cada paso te quedas con la mitad donde puede estar el que buscas. ¿Cuántos pasos necesitas, más o menos?
4. Completa el código
Completa para mirar el número que está a la mitad entre izq y der.
5. Ordena las líneas
Ordena una función que cuente cuántas veces se puede partir n a la mitad hasta llegar a 1.
6. Encuentra el bug
Debería contar cuántas veces se parte 64 a la mitad hasta llegar a 1, o sea 6. ¿Qué línea tiene el error?
7. Opción múltiple
¿Qué etiqueta le toca a sorted(nums)?
8. Predice la salida
¿Qué imprime este código?

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