Materias · 🏛️ Universidad y trabajo
Complejidad (Big O)
Ejercicios resueltos de Complejidad (Big O) paso a paso, con el error que más se comete en cada uno: Notación Big O, Comparar algoritmos por su crecimiento y más. Gratis y en español.
Preguntarle al tutor de Complejidad (Big O)Sin instalar nada. Puedes probar antes de crear cuenta.
Ejercicios resueltos de Complejidad (Big O)
Resueltos paso a paso, como te los explicaría el tutor, y con el error que más se comete.
Notación Big O
¿Cuántas veces se ejecuta la línea de adentro y cuál es la complejidad?
for i in range(n):
for j in range(i):
total += 1
Cómo se resuelve
- 1El bucle de afuera fija i desde 0 hasta n − 1. El de adentro NO da n vueltas: da exactamente i vueltas, así que el trabajo cambia en cada pasada y no se puede multiplicar n por n sin más.
- 2Se suman las vueltas una por una: con i = 0 son 0 vueltas, con i = 1 es 1, con i = 2 son 2… y con i = n − 1 son n − 1.
- 3El total es 0 + 1 + 2 + … + (n − 1), que por la fórmula de Gauss vale n(n − 1)/2.
- 4Desarrollando queda (n² − n)/2 = n²/2 − n/2.
- 5Big O se queda con el término que manda cuando n crece y descarta las constantes multiplicativas: de n²/2 − n/2 sobrevive n². La complejidad es O(n²).
- 6Comprobación con n = 1.000: 1.000 × 999 / 2 = 499.500 ejecuciones, frente al 1.000.000 del doble bucle completo. Es prácticamente la mitad, y una mitad es una constante.
Respuesta: La línea se ejecuta n(n − 1)/2 veces y la complejidad es O(n²).
El error de siempre: Ver que el bucle interno «solo llega hasta i» y concluir que entonces es O(n log n) o incluso O(n). Hacer la mitad del trabajo de un doble bucle completo sigue siendo cuadrático: 499.500 y 1.000.000 crecen al mismo ritmo y solo se diferencian en el factor 1/2, que Big O no mira.
Comparar algoritmos por su crecimiento
Un proceso que ordena registros tarda 2 segundos con 10.000 registros usando un algoritmo O(n²). Ahora hay que procesar 1.000.000 de registros. ¿Cuánto tardaría? ¿Y si el mismo computador corriera un algoritmo O(n log n) que con 10.000 registros también tarda 2 segundos?
Cómo se resuelve
- 1Big O no da segundos, da cómo crece el tiempo. Sirve justo para esto: comparar el mismo programa consigo mismo cuando cambia el tamaño de la entrada.
- 2El tamaño pasa de 10.000 a 1.000.000, o sea que n se multiplica por 100.
- 3Con O(n²) el tiempo crece como el cuadrado de n: si n se multiplica por 100, el tiempo se multiplica por 100² = 10.000.
- 42 s × 10.000 = 20.000 s. Dividido entre 3.600 da 5,56 horas, es decir unas 5 horas y media.
- 5Con O(n log n) el factor es 100 × (log 1.000.000 ÷ log 10.000). Como 1.000.000 = 10⁶ y 10.000 = 10⁴, ese cociente es 6/4 = 1,5, y da igual en qué base se tome el logaritmo.
- 6Factor total: 100 × 1,5 = 150. Tiempo: 2 s × 150 = 300 s, o sea 5 minutos.
Respuesta: El algoritmo O(n²) pasaría de 2 segundos a 20.000 segundos (unas 5 horas y media). El O(n log n) pasaría a 300 segundos, 5 minutos.
El error de siempre: Pensar que si los datos se multiplican por 100 el tiempo también se multiplica por 100 y responder 200 segundos. Esa regla de tres solo vale para algoritmos lineales, O(n). Con O(n²) el factor es el cuadrado, y ahí es donde un programa que «iba bien en las pruebas» con datos chiquitos se cae el día que le llegan los datos de verdad.
¿Y si tu ejercicio no es ninguno de estos?
No hace falta buscar el ejercicio exacto en internet. Trae el tuyo, o pide los que te falten.
Todo esto es gratis y sin instalar nada. Puedes probar antes de crear cuenta.
Lo que cubre
- Notación Big O
- Comparar algoritmos por su crecimiento
Preguntas que le puedes hacer
- Notación Big OExplícame «Notación Big O» con un ejemplo práctico y dime en qué suele equivocarse la gente.
- Comparar algoritmos p…Explícame «Comparar algoritmos por su crecimiento» con un ejemplo práctico y dime en qué suele equivocarse la gente.
Cómo enseña este tutor
Es riguroso y completo: justifica cada paso y nombra el teorema, la norma o la buena práctica que está aplicando, para que puedas citarla en tu trabajo o en el parcial.
- · Te muestra el camino completo, no solo el resultado.
- · Si algo no te cuadra, te lo explica otra vez de otra manera.
- · Con una foto de tu cuaderno te dice dónde está el error.
- · Te arma quizzes de lo que acabas de ver para saber si de verdad quedó.
Otras materias de Universidad y trabajo
