07 · ¿Cuánto se demora tu programa?
Buscar soluciones eficientes · Ruta de Aprendizaje
Antes de empezar. Ciclos y recorridos de arreglos: 03 - Arreglos y búsqueda lineal. Basta reconocer qué hacen for, while, if y un acceso como a[i]; el conteo de trabajo y la notación se desarrollan aquí desde ejemplos.
🎯 Objetivos
Al terminar este módulo sabes:
- Estimar cuántas operaciones hace tu código (notación O grande, sin sustos).
- Estimar con las restricciones si un enfoque es viable antes de programarlo.
- Reconocer cuándo un ciclo se reemplaza por una fórmula.
📖 La lección
Primero: ¿qué queremos estimar?
En una competencia, cada participante obtiene un puntaje. Queremos calcular la suma de todos los puntajes. Si son cuatro —2, 5, 1 y 4—, podemos sumarlos a mano: el total es 12.
Ahora imagina que participan 200 000 personas. Un programa puede hacer la misma suma, leyendo un puntaje y agregándolo al total cada vez. ¿Cuántas sumas tendrá que hacer? ¿Podrá terminar dentro de los 2 segundos que permite el problema?
Para responder, empezaremos siguiendo el caso de cuatro participantes. Después veremos cómo cambia la cantidad de trabajo cuando participan más.
En este ejemplo hay tres cantidades distintas:
- Tamaño de la entrada: la cantidad de puntajes que recibimos, uno por participante.
- Trabajo del algoritmo: cuántas lecturas y sumas hacemos para obtener el total.
- Tiempo real: los segundos que tarda el computador en hacer ese trabajo.
Podemos contar el trabajo leyendo el código. Convertirlo a segundos exige suposiciones sobre la máquina y después mediciones. Empezaremos por la parte que podemos justificar sin ejecutar: cuántas veces ocurre cada trabajo.
Llamaremos n a la cantidad de participantes: en el ejemplo pequeño, n=4.
El valor de un puntaje no cambia esa cantidad: aunque una persona obtenga
un millón de puntos, seguimos leyendo un solo puntaje por persona.
Contar operaciones
Guardamos los cuatro puntajes en a = {2, 5, 1, 4}. Para sumar los de
cualquier competencia necesitamos leerlos todos: empezamos con suma cero y agregamos cada elemento.
// supone: vector<int> a; // para la traza: {2, 5, 1, 4}
long long suma = 0;
for (int i = 0; i < (int)a.size(); i++)
suma += a[i];
cout << suma << "\n"; // 12 para la traza| Vuelta | Índice i | Valor leído | Suma después |
|---|---|---|---|
| 1 | 0 | 2 | 2 |
| 2 | 1 | 5 | 7 |
| 3 | 2 | 1 | 8 |
| 4 | 3 | 4 | 12 |
Con cuatro elementos se ejecuta cuatro veces suma += a[i]; con n elementos,
n veces. Supondremos que cada acceso al vector y suma de enteros de tamaño
fijo cuesta una cantidad constante de trabajo y que la suma cabe en long long.
También se inicializa i, se compara con el límite y se incrementa. No estamos
contando instrucciones exactas del procesador: elegimos una operación
representativa. Esos trabajos adicionales cambian el costo de cada vuelta,
pero duplicar n sigue duplicando aproximadamente el trabajo del recorrido.
Con un vector vacío, el cuerpo se ejecuta cero veces, aunque iniciar y terminar
el programa todavía tiene un costo.
Ciclos consecutivos: sumar los trabajos
Si primero recorremos n datos y después recorremos m datos, los trabajos se suman. Este contador hace visible cuántas vueltas se ejecutan:
// supone: int n, m; // cantidades no negativas
long long revisiones = 0;
for (int i = 0; i < n; i++) revisiones++;
for (int j = 0; j < m; j++) revisiones++;
cout << revisiones << "\n"; // n + mCon n=4 y m=3, hay 4 + 3 = 7 revisiones. El segundo ciclo comienza cuando el primero ya terminó. Si ambos recorren el mismo vector de tamaño n, son n+n = 2n, no n². Leer el vector y después buscar en él es un ejemplo de trabajos consecutivos.
Ciclos anidados: contar lo que se repite por cada vuelta
Ahora cada vuelta exterior ejecuta todo el ciclo interior:
// supone: int n, m; // cantidades no negativas
long long revisiones = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
revisiones++;
cout << revisiones << "\n"; // 1LL * n * mCon n=4 y m=3, para cada uno de los cuatro valores de i se prueban tres valores de j: 3+3+3+3 = 12 revisiones. Son n·m en total. Recorrer una matriz de n filas y m columnas tiene esta forma.
Si ambos límites son n, hay n·n = n² vueltas. En el dibujo fijamos n=4: una fila representa un recorrido; el cuadrado representa combinar cada índice con cada uno de los cuatro índices del otro ciclo.
Si el diagrama no cabe, deslízalo horizontalmente.
No multiplicamos porque haya dos palabras for: multiplicamos porque el
ciclo interior realiza m vueltas por cada una de las n vueltas exteriores.
Si su límite cambia, hay que contar de otra manera.
Cuando el ciclo interior no siempre hace lo mismo
Para comparar cada pareja de posiciones distintas una sola vez, podemos exigir que j esté después de i:
// supone: int n; // cantidad no negativa
long long parejas = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
parejas++;
cout << parejas << "\n";Para n=4:
i | Valores de j | Parejas nuevas |
|---|---|---|
| 0 | 1, 2, 3 | 3 |
| 1 | 2, 3 | 2 |
| 2 | 3 | 1 |
| 3 | ninguno | 0 |
El total es 3+2+1+0 = 6, no 16. Para n posiciones es
(n−1)+(n−2)+…+1 = n(n−1)/2. Podemos justificar la división por dos:
hay n(n−1) elecciones ordenadas de dos posiciones distintas, pero cada pareja
aparece dos veces, como (i,j) y como (j,i).
En cambio, si por cada i el ciclo interior hace como máximo tres revisiones, el total no supera 3n. Aunque haya dos ciclos anidados, ese trabajo crece proporcionalmente a n. Al final de la página hay código para contrastar ambos casos.
Resumir el crecimiento: la notación O grande
Las cuentas anteriores nos permiten comparar qué ocurre cuando crece la entrada. La notación O grande expresa una cota de ese crecimiento. En esta guía buscaremos una cota que describa bien el trabajo, omitiendo factores constantes y términos que crecen más lentamente.
| Trabajo contado | Cómo lo resumimos | Qué significa |
|---|---|---|
| Una cantidad fija de operaciones | O(1) | no aumenta con n |
| n, 2n o 3n revisiones | O(n) | crecimiento lineal |
| n² o n(n−1)/2 revisiones | O(n²) | crecimiento cuadrático |
| n+m revisiones | O(n+m) | cuenta ambos tamaños |
| n·m revisiones | O(n·m) | combina ambos tamaños |
En la cota O(n·m) para recorrer una matriz suponemos dimensiones positivas. Si m=0, no se ejecuta el cuerpo interior, pero el ciclo exterior todavía recorre sus n vueltas: también hay que contar ese trabajo.
O(1) no significa una sola operación: diez sumas fijas también tienen costo constante respecto de n. O(n) no significa n segundos, ni que dos programas O(n) tarden exactamente lo mismo.
Si un programa hace n² + 3n + 5 unidades de trabajo, para n=1000 los términos
son 1000000, 3000 y 5. El término cuadrático domina al crecer n: resumimos el
total como O(n²). Eso permite comparar enfoques sin fingir que conocemos
cada instrucción de la máquina. Al medir tiempos reales, los factores
constantes vuelven a importar.
Mejor caso, peor caso y decisiones del programa
Buscar linealmente un valor ilustra por qué el tamaño no basta para predecir una ejecución exacta. En un vector de n elementos:
- Si está primero, basta una comparación.
- Si está al final o no aparece, hacen falta n comparaciones.
El mejor caso es O(1) y el peor, O(n). Para decidir si una solución soporta los límites, normalmente analizamos el peor caso permitido, no solo la entrada de ejemplo. Decir «en promedio se encuentra rápido» necesita justificar qué distribución de entradas estamos suponiendo; el juez no promete esa distribución.
En un if/else se ejecuta una sola rama. Para una cota del peor caso contamos
la condición y la más costosa de las ramas que pueda ejecutarse. Si una recorre
n datos y la otra hace tres operaciones, la cota es O(n). Si la condición también
hace una búsqueda, su costo se incluye: no todas las condiciones son O(1).
Qué significa ese logaritmo
Ya contamos ciclos que avanzan de uno en uno. Ahora pensemos en un proceso que divide el trabajo pendiente por dos en cada vuelta:
// supone: int n; // n >= 1
int pendientes = n, pasos = 0;
while (pendientes > 1) {
pendientes /= 2; // división entera
pasos++;
}
cout << pasos << "\n";Con n=16, los tamaños pendientes son 16→8→4→2→1. El cuerpo se ejecuta cuatro veces, aunque empezó con 16 elementos. El dibujo representa tamaños, no un arreglo que el programa esté copiando:
Si el diagrama no cabe, deslízalo horizontalmente.
| n inicial | 8 | 16 | 32 | 1024 |
|---|---|---|---|---|
| Divisiones hasta 1 | 3 | 4 | 5 | 10 |
Duplicar n añade una sola vuelta. A esa relación le damos un nombre: log₂(n) es el exponente al que hay que elevar 2 para obtener n. Como 2⁴=16, log₂(16)=4. Para potencias de dos coincide exactamente con la cantidad de divisiones del ejemplo.
Si n no es una potencia de dos, importa cómo redondea el código: con 15, la división entera recorre 15→7→3→1 y hace 3 vueltas. Una versión que redondee hacia arriba puede hacer una más. Ambas tienen crecimiento O(log n). Con un millón, este código hace 19 vueltas; como 2²⁰=1048576, «unas 20» es una buena estimación de escala.
Dividir por dos solo da ese costo cuando cada vuelta hace trabajo constante. Si primero recorres todos los pendientes y luego los divides, el trabajo es n+n/2+n/4+…: para n potencia de dos, hasta procesar también el último elemento, suma 2n−1, y el total es O(n).
La búsqueda binaria aprovechará este crecimiento: en un arreglo ordenado, una comparación permite descartar aproximadamente la mitad de los candidatos. Aquí estamos contando su trabajo; el siguiente módulo desarrolla cómo hacer ese descarte correctamente.
También importa el trabajo dentro del ciclo
Un ciclo de n vueltas cuesta «n por el costo de cada vuelta» si ese costo es el mismo o está acotado del mismo modo en todas ellas. Una línea de C++ puede ocultar mucho trabajo:
| Trabajo realizado | Costo que debemos contar |
|---|---|
Leer a[i], comparar o sumar enteros de tamaño fijo | O(1) |
| Buscar linealmente en n elementos | O(n) en el peor caso |
| Copiar un vector de n enteros | O(n) |
Ordenar n enteros con sort | O(n log n) |
Buscar o insertar una clave entera en un set con hasta n elementos | O(log(n+1)) |
Por ejemplo, si haces una copia completa de un vector de n elementos en cada una de n vueltas, realizas n·n = O(n²) trabajo, aunque visualmente solo haya un ciclo. Si en cada vuelta haces una búsqueda de costo O(log n), obtienes O(n log n). Ese producto combina n repeticiones con trabajo logarítmico en cada una.
El costo de sort es el contrato de la herramienta para ordenar: no necesitas
conocer su implementación para incluirlo en la cuenta. Con n=200000,
log₂(n)≈18 y n·log₂(n)≈3600000 da una escala útil, no un número exacto de
comparaciones. En fórmulas de complejidad se suele escribir log sin base:
cambiar una base fija mayor que uno solo multiplica por una constante.
Los tipos también importan: comparar dos enteros tiene costo constante en este modelo; comparar strings puede recorrer varios caracteres. Las cuentas de la tabla suponen valores y comparaciones de costo constante.
Varias consultas y varios casos de prueba
Queremos responder q preguntas de pertenencia sobre n datos que no cambian. Una búsqueda lineal por pregunta cuesta O(nq). Otra opción es ordenar una vez y hacer q búsquedas binarias: O(n log n + q log n). La preparación y las consultas son trabajos consecutivos; por eso sumamos sus costos.
Con n=q=200000, el primer plan puede hacer 40000000000 comparaciones. El segundo tiene una escala de unos 3600000 para ordenar y otros 3600000 para las consultas. Si q=1, en cambio, recorrer una vez O(n) evita pagar la ordenación. No siempre compensa preparar una estructura más elaborada.
Si hay varios casos de prueba, sumamos el trabajo de todos. Con tamaños n₁, n₂, … y un algoritmo cuadrático por caso, el total depende de n₁²+n₂²+…, no solo del caso más grande. Por ejemplo, dos casos de tamaño 1000 hacen 2000000 revisiones cuadráticas en total.
Lee también los límites sobre la suma de tamaños. Un algoritmo lineal procesa como máximo N elementos si el enunciado garantiza que la suma de n no supera N. Para uno cuadrático, repartir los mismos datos cambia el costo: un caso de tamaño 2000 hace 4000000 revisiones; dos de tamaño 1000 hacen 2000000.
Del conteo al límite de tiempo
Volvamos a los 200 000 participantes y al límite de 2 segundos. Sumar sus puntajes requiere un recorrido. Si la pregunta fuera ordenarlos o comparar cada participante con todos los demás, el trabajo sería distinto:
| Plan | Escala de trabajo con ese n |
|---|---|
| Un recorrido | 200000 |
| Ordenar | unos 3600000, usando n·log₂(n) |
| Comparar todas las parejas con ambos índices independientes | 40000000000 |
La diferencia entre doscientas mil y cuarenta mil millones ya es suficiente para descartar muchas ideas. No necesitas adivinar décimas de segundo para notar que el tercer plan hace muchísimo más trabajo.
Como modelo ilustrativo, supongamos una tasa de 10⁸ operaciones simples por segundo. Dividir el trabajo por esa tasa daría 400 segundos para 4·10¹⁰ operaciones. Bajo esa estimación, ese plan queda muy lejos de un límite de 2 segundos. La tasa no es una garantía: depende del procesador, compilador, memoria, entrada/salida y de qué llames «operación». No es igual sumar un entero que insertar en un mapa o comparar strings largos.
Para un enfoque cercano al límite, usa una medición con datos grandes y construidos para provocar su peor caso. Compila en condiciones similares a las del juez, evita salida de depuración y repite la medición. Probar n y 2n ayuda a contrastar el modelo: un trabajo lineal tiende a duplicarse; uno cuadrático, a cuadruplicarse cuando domina el trabajo principal. Tu computador no es el juez, así que deja margen. Un contador didáctico que siempre termina valiendo n² puede ser simplificado por el compilador: no sirve por sí solo como benchmark del algoritmo real.
En una terminal de Linux, macOS o WSL, una medición puede hacerse así:
g++ -O2 -std=c++17 sol.cpp -o sol
/usr/bin/time -p ./sol < grande.txt > salida.txtsol.cpp es tu solución y grande.txt debe contener una entrada válida que
hayas preparado. salida.txt recibe la respuesta del programa; time informa
los tiempos por separado. real son segundos transcurridos; user y sys
son tiempos de CPU. Ajusta las opciones de compilación a las del juez y
comprueba también que la respuesta guardada sea correcta.
Tiempo y memoria se revisan por separado. Un recorrido puede necesitar solo un acumulador adicional; guardar una tabla n×n requiere n² casillas aunque cada consulta posterior sea rápida. Cuenta todos los arreglos que estarán vivos a la vez. Las estimaciones en bytes están en memoria de vectores y memoria de matrices.
De ciclo a fórmula
A veces no hace falta recorrer. Queremos saber cuántos incrementos de uno
faltan para que a sea divisible por b, con 0≤a≤10⁹ y 1≤b≤10⁹.
El operador % devuelve el resto de la división: 7 % 5 = 2.
Podemos incrementar hasta encontrar un múltiplo. Con a=7 y b=5, probamos 8, 9 y 10: tres incrementos. Pero con a=1 y b=10⁹ serían 999999999. El costo de esa simulación depende de b, no de la cantidad de números de entrada: puede hacer hasta b−1 incrementos.
El resto dice cuánto avanzamos desde el múltiplo anterior. Si no es cero,
faltan b - resto pasos para el siguiente. Si es cero, ya terminamos y faltan cero:
// supone: long long a, b; // 0 <= a <= 1000000000; 1 <= b <= 1000000000
cout << (b - a % b) % b << "\n";Si el diagrama no cabe, deslízalo horizontalmente.
El % b final convierte b en 0 cuando a ya era múltiplo; en los otros casos
no cambia la respuesta, que está entre 1 y b−1. Hacemos un número fijo de
operaciones con enteros de tamaño fijo: O(1) tiempo y memoria adicional.
La mejora viene de responder la misma pregunta sin simular cada incremento.
Cómo analizar tu propio programa
- Identifica qué puede crecer: n datos, n×m casillas, q consultas, valores numéricos.
- Cuenta cuántas veces se realiza cada trabajo. Revisa los límites de los ciclos, incluyendo si avanzan de uno en uno, saltan o se reducen.
- Incluye el costo del cuerpo: llamadas a funciones, copias, búsquedas y ordenaciones.
- Suma fases consecutivas y casos de prueba; para decisiones, considera la rama más costosa posible.
- Resume el crecimiento con O grande y sustituye los máximos del enunciado para estimar la escala.
- Comprueba memoria y, si el tiempo está cerca del límite, mide el algoritmo con entradas exigentes.
No basta que el programa sea rápido: primero debe dar la respuesta correcta. Y un algoritmo O(n²) no está prohibido: puede ser apropiado para unos cientos de elementos. La pregunta es si su trabajo para los límites de este problema cabe en los recursos disponibles.
La guía Complejidad computacional amplía costos de la biblioteca, análisis amortizado y otras familias de crecimiento. Esta clase deja las herramientas para analizar los recorridos, búsquedas y ordenaciones que ya puedes escribir.
🏋️ Práctica
Práctica directa: Contar y comparar
Para n=4 y m=3, predice las salidas de los contadores de ciclos consecutivos, anidados y parejas. Después reemplaza n y m por 4000 y 3000 y estima las salidas sin ejecutarlos. Indica qué cuenta cada número y su complejidad.
Contrastar las cuentas
Consecutivos: 7 y 7000, O(n+m). Anidados: 12 y 12000000, O(n·m). Parejas de un vector de tamaño n: 6 y 7998000, O(n²). El contador de parejas no usa m. Ninguna de esas salidas es un tiempo en segundos.
Aplicar una fórmula: El siguiente múltiplo
Lee a,b con 0≤a≤10⁹, 1≤b≤10⁹. Imprime cuántos +1 faltan para que a sea múltiplo de b. Entrada: 10 6. Salida: 2.
Idea para comprobar tu solución
El resto es 4; faltan 6−4=2. El caso
12 6debe dar 0: usa el resto final de la fórmula.
Variación: Evaluar dos planes
Recibes n=200000 datos y q=200000 preguntas de pertenencia. Un plan recorre todo por pregunta; otro ordena una vez y busca binariamente. Estima ambos costos. Después repite con q=1.
Una pista, si la necesitas
Incluye el costo de preparar los datos, aunque se pague solo una vez.
Contrastar el razonamiento
Con muchas preguntas: O(nq) frente a O(n log n + q log n). Con una sola, recorrer O(n) evita ordenar O(n log n). Las restricciones y la cantidad de consultas cambian qué preparación conviene.
Aplicar en problemas
Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.
Problemas OCI reales, en español (cada nota trae el link a su mirror):
| # | Problema | Fase | Qué practica |
|---|---|---|---|
| 1 | Contraseña | Regional 2022 | componer 10⁴ reglas en UN mapeo (la lección en vivo) |
| 2 | Ocimatic | Regional 2017 | desafío: justificar que tu plan alcanza con D hasta 10¹⁰ |
| 3 | ⭐ Mega Woman | Regional 2018 | ecuación en vez de simular 10¹² pasos |
Más aplicaciones (en inglés)
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Divisibility Problem (1328A) | ★ (800) | el ciclo que da TLE y la fórmula que no |
| 2 | Elephant (617A) | ★ (800) | O(1) con división hacia arriba |
| 3 | Again Twenty Five! (630A) | ★★ (800) | descubrir que la respuesta es constante |
| 4 | ⭐ Lucky Division (122A) | ★★ (1000) | fuerza bruta que SÍ cabe (y saber por qué) |
Un ejemplo para pensar
Para cada posición i de un arreglo de tamaño n, un ciclo interior
revisa únicamente las tres posiciones siguientes que existan. Hay dos
ciclos anidados: ¿el trabajo es necesariamente cuadrático?
Compara el código y predice su salida antes de ejecutarlo:
int n = 6;
int revisionesA = 0, revisionesB = 0;
// A: hasta tres posiciones después de i.
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n && j <= i + 3; j++)
revisionesA++;
// B: todas las posiciones después de i.
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
revisionesB++;
cout << revisionesA << " " << revisionesB << "\n";Contar repeticiones, no niveles de indentación
Cada una de las
nposiciones provoca a lo sumo tres revisiones: no más de3nen total. Es O(n). Si el ciclo interior revisara todas las posiciones posteriores, haría(n−1) + (n−2) + … + 1 = n(n−1)/2revisiones, que sí es O(n²). Lo decisivo es cuántas veces se ejecuta el cuerpo, no cuántos ciclos se ven en el código.
← 06 - Conjuntos, mapas y pares · Ruta de Aprendizaje · 08 - Búsqueda binaria →