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
Úsala con tu clase: tus estudiantes la abren con un enlace o un código QR, sin crear una cuenta.
Sigue con Algoritmos y resolución de problemas
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.
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 cuatro ritmos de crecimiento: log₂n apenas sube, n crece en proporción, n·log₂n crece algo más rápido y n² se multiplica por cuatro cada vez que n se duplica. Las mediciones confirman la teoría: en un arreglo aleatorio, burbuja hace unas n²/2 comparaciones y quicksort unas 1,4·n·log₂n. Con n pequeño la diferencia casi no importa; con muchos datos, elegir el algoritmo decide si un programa tarda segundos u horas.
Cómo usarla
Empieza con Curvas teóricas mostradas en las cuatro funciones y arrastra sobre el gráfico para cambiar n, leyendo el valor de cada curva. Cuando las curvas estén demasiado separadas para compararlas, activa Escala logarítmica en el eje de pasos. Después pulsa Carrera para que ambos algoritmos ordenen el mismo arreglo al mismo ritmo de pasos, y repite con Nuevo arreglo y un n mayor para ver cómo crece la ventaja.
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
- Escala logarítmica en el eje de pasos
- Velocidad de la carrera 5–200 pasos/s
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?
