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

Usar con mi clase

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

  1. ¿Por cuánto se multiplica n² cuando n pasa de 50 a 100, y aproximadamente por cuánto se multiplica n·log₂n?
  2. ¿Por qué la curva log₂n se mantiene casi plana mientras la curva n² sube con fuerza?
  3. Con n = 10, ¿cuántas comparaciones más hace burbuja que quicksort, y importa esa diferencia en la práctica?