O(1) y O(n)

Python · Unidad 22: Complejidad

Cuando los pasos crecen igual que los datos, se escribe O(n) y se lee "orden de n". Es una etiqueta del ritmo, no del número exacto.

Son las mismas etiquetas que trae cada reto de la app: O(1), O(log n), O(n), O(n log n), O(n²) y O(2ⁿ), de la más barata a la más cara.

compras = [12, 5, 9]
pasos = 0
for p in compras:
    pasos += 1
print(pasos, len(compras))

Imprime

3 3

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. Opción múltiple
nums es una lista de números. ¿Cuál de estas operaciones cuesta lo mismo con 3 números que con un millón?
3. Predice la salida
¿Qué imprime este código?
4. Completa el código
Completa para regresar el último precio sin recorrer la lista.
5. Predice la salida
¿Qué imprime este código?
6. Ordena las líneas
Ordena una función O(n) que cuente cuántos números pares hay en la lista.
7. Encuentra el bug
Debería imprimir el primero y el último de la lista. ¿Qué línea tiene el error?
8. Encuentra el caso que falla
contiene(nums, x) debería regresar True si x está en la lista y False si no, mirando uno por uno. ¿Con qué llamada falla?
9. Opción múltiple
Las dos regresan el último número de la lista. ¿Cuál es O(1)?

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