Big-O — nombra la complejidad del código
Lee el fragmento, nombra su complejidad temporal y mira la curva de crecimiento. Seis clases, seis rondas. Gratis.
Cinco fragmentos, cinco de las seis clases, cada una preguntada una vez.
Cómo jugar
- Lee el fragmento y elige su complejidad temporal entre las seis.
- La curva de crecimiento se dibuja tras cada respuesta: la tuya en rojo, la correcta en verde.
- Cinco de las seis clases por partida, sin repetir, así que responder siempre lo mismo acierta como mucho una vez.
- Las respuestas correctas seguidas pagan más. Una equivocada reinicia la racha.
Cómo funciona
Cada ronda muestra un fragmento corto de código y pregunta por su complejidad temporal. Respondes y se dibuja la curva de crecimiento — la tuya frente a la correcta — de modo que la elección deja de ser una etiqueta y pasa a ser una forma que puedes ver. Una partida pregunta cinco de las seis clases, barajadas y sin repetir, así que responder siempre lo mismo acierta como mucho una vez — y la clase que se queda fuera cambia, de modo que la última ronda nunca sale gratis por descarte. Los fragmentos están elegidos para que cada uno tenga una única respuesta defendible: sin salidas anticipadas, sin costes de biblioteca ocultos y sin nada que delate su propia complejidad en un comentario. La ordenación se toma como O(n log n) en todo momento, que es lo que ofrece cualquier biblioteca estándar. Se ejecuta en tu dispositivo, no se envía nada y no hace falta registrarse.
La notación O describe cómo crece el coste, no cuánto vale. Un O(n²) con buenas constantes gana a un O(n log n) hinchado en los tamaños que ve la mayoría del código real, que es el tema de otro juego de este sitio.
Preguntas frecuentes
¿Por qué la curva está en escala logarítmica?
Porque si no, seis clases no caben en un mismo gráfico. Con n=24 una función de tiempo constante cuesta 1 y una exponencial cuesta dieciséis millones, así que en un eje lineal cinco de las seis curvas serían la misma línea plana pegada abajo. La escala logarítmica convierte cada clase en una pendiente distinguible, que es lo que merece la pena ver.
¿La ordenación es realmente O(n log n)?
Para las ordenaciones por comparación, sí: es una cota inferior demostrada y es lo que ofrece cualquier biblioteca estándar. Las ordenaciones por conteo y radix la superan porque no comparan, pero necesitan suposiciones sobre las claves. Cuando un fragmento de aquí llama a sort(), cuesta n log n.
¿Por qué no hay fragmentos con salida anticipada?
Porque una salida anticipada convierte un peor caso en un caso medio, y entonces la respuesta no es una única clase. Una búsqueda lineal que retorna en la primera coincidencia es O(n) en el peor caso y O(1) si la coincidencia siempre está la primera, así que preguntar por «la» complejidad sería injusto. La búsqueda binaria es la excepción: sale antes y sigue siendo exactamente O(log n).
¿Importa la racha?
Sí. Cada segunda respuesta correcta seguida aumenta lo que paga la siguiente, hasta un tope, así que una partida limpia vale bastante más que cuatro aciertos y dos fallos. Un fallo la reinicia.