Complejidad de algoritmos – O(log n), O(n), O(n log n), O(n²) y una carrera de ordenamiento
InformáticaAlgoritmos y resolución de problemasEdades 15–16
¿Para qué usas principalmente esta simulación?
Úsala con tu clase: tus estudiantes la abren con un enlace o un código QR, sin crear una cuenta.
Un gráfico representa el número de pasos frente al tamaño de entrada n para las funciones log₂n, n, n·log₂n y n², junto con el número de comparaciones medido en vivo para el ordenamiento de burbuja y quicksort. Los estudiantes arrastran el marcador de n en el gráfico para leer los valores y luego pulsan Carrera para ver cómo ambos algoritmos ordenan el mismo arreglo al mismo ritmo de pasos: quicksort (n log n) termina antes que el de burbuja (n²), y la diferencia crece al aumentar n. Una segunda pantalla, Problema del viajante, coloca ciudades en un mapa y compara la fuerza bruta, que revisa los (n − 1)!/2 recorridos y pronto necesita un tiempo no razonable, con la rápida heurística del vecino más cercano.
Lección: Evaluación de algoritmos: número de operaciones frente al tamaño de entrada, notación O grande, comparación entre burbuja y quicksort
Qué muestra
La complejidad de un algoritmo describe cómo crece el número de operaciones cuando aumenta el tamaño de los datos n, sin tener en cuenta los factores constantes. El gráfico compara log₂n, n, n·log₂n y n²; las mediciones muestran que burbuja hace unas n²/2 comparaciones y quicksort unas 1,4·n·log₂n. Algunos problemas son mucho peores. La pantalla del problema del viajante prueba todos los recorridos, que son (n − 1)!/2: cada ciudad más multiplica el trabajo y 16 ciudades llevarían horas. Una heurística como el vecino más cercano responde en n(n − 1)/2 pasos, rápido pero no siempre con el recorrido más corto.
Cómo usarla
Arrastra sobre el gráfico para cambiar n y activa Escala logarítmica cuando las curvas estén muy separadas; pulsa Carrera para ver los ordenamientos. Luego pulsa Viajante: toca el mapa para añadir ciudades, pulsa Fuerza bruta y Vecino más cercano, y compara los recorridos y los pasos. Cambia Número de ciudades y Velocidad de la computadora para ver cómo se dispara el tiempo.
Parámetros que puedes cambiar
- Tamaño de los datos n 4–100
- Curvas teóricas mostradas log₂n, n, n·log₂n, n², n y n², log₂n, n y n·log₂n, n, n², 2ⁿ y n!
- Escala logarítmica en el eje de pasos
- Velocidad de la carrera 5–200 pasos/s
- Pantalla Gráfico de complejidad, Problema del viajante
- Número de ciudades (problema del viajante) 4–16
- Semilla aleatoria de las ciudades 1–999
- Velocidad de la computadora 10⁶ pasos por segundo, 10⁹ pasos por segundo, 10¹² pasos por segundo
Preguntas para explorar
- ¿Por cuánto se multiplica n² cuando n pasa de 50 a 100, y aproximadamente por cuánto se multiplica n·log₂n?
- ¿Por qué la curva log₂n se mantiene casi plana mientras la curva n² sube con fuerza?
- Con n = 10, ¿cuántas comparaciones más hace burbuja que quicksort, y importa esa diferencia en la práctica?