⏱️ Complejidad computacional

Guía de referencia para predecir si un programa pasa en tiempo y memoria antes de escribirlo. La versión introductoria y con práctica guiada está en la ruta: 07 - Cuánto se demora tu programa. Volver a Referencia.

El modelo: contar operaciones

No existe una conversión universal entre operaciones y segundos. Una suma, una comparación de cadenas y una inserción en un map no cuestan lo mismo. Cuenta el trabajo del peor caso permitido, considera todos los casos de prueba y contrasta la estimación con el límite de tiempo. Un orden de magnitud sirve para descartar planes inviables; no garantiza que un programa pase.

Cómo contar: tres reglas

Casi todo el análisis sale de aplicar estas tres:

  1. Ciclos anidados multiplican. Un for de n dentro de otro de n es n·n.
  2. Bloques en secuencia: manda el peor. O(n) seguido de O(n²) es O(n²) — por eso optimizar la parte barata no cambia nada.
  3. Un ciclo que duplica (o divide) es logarítmico. Avanzar i *= 2 llega a n en ~log₂ n vueltas: para n = 10⁶ son 20, no un millón.
for (int i = 0; i < n; i++)          // O(n)
    for (int j = 0; j < n; j++)      // ...dentro de otro: O(n²)
        hacer_algo();
 
for (int i = 0; i < n; i++) a();     // O(n)
for (int i = 0; i < n; i++)          // seguido de O(n²)
    for (int j = 0; j < n; j++) b(); // el total es O(n²): manda el peor
 
for (int i = 1; i <= n; i *= 2)      // 1, 2, 4, 8, ...: O(log n)
    hacer_algo();

⚠️ El que engaña: for (int j = i; j < n; j++) dentro de un ciclo de i recorre “medio cuadrado” (n²/2 pasos), pero O grande ignora el /2 — sigue siendo O(n²). Ojo con creer que es lineal porque el interior “es más corto”.

Notación O grande

O(f(n)) describe cómo escala el trabajo cuando n crece: se queda solo el término dominante y se ignoran las constantes (O(3n² + 5n) = O(n²)). Eso hace el análisis portable entre máquinas… y también significa que las constantes no son gratis en la práctica (ver Trampas, abajo).

Si quieres el rigor: formalmente, f(n) es O(g(n)) si existen constantes c y n₀ tales que f(n) ≤ c·g(n) para todo n ≥ n₀. Como es una cota superior, decir que la búsqueda binaria es “O(n²)” es técnicamente cierto e inútil: siempre se busca la cota más ajustada.

Catálogo de clases (con su ejemplo canónico)

ClaseEjemploTrabajo aproximado en un tamaño concreto
O(1)acceso a[i]una operación, si el índice existe
O(log n)búsqueda binariaunas 20 divisiones para n = 10⁶
O(√n)probar divisoreshasta 10⁶ candidatos para n = 10¹²
O(n)un recorrido10⁶ visitas para n = 10⁶
O(n log n)sortorden de 3,6 millones para n = 2·10⁵
O(n²)comparar todos los pareshasta 25 millones para n = 5000
O(n³)Floyd-Warshall64 millones para n = 400
O(2ⁿ)enumerar subconjuntoscerca de un millón para n = 20
O(n!)enumerar permutaciones3 628 800 para n = 10

La última columna cuenta trabajo orientativo, no segundos. Procesar cada subconjunto o permutación también puede costar O(n): enumerarlos no implica que toda la solución cueste O(2ⁿ) u O(n!).

Dos de esos, en código:

// O(sqrt(n)): primalidad probando divisores hasta la raíz
bool es_primo(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i <= n / i; i++)
        if (n % i == 0) return false;
    return true;
}
 
// O(2^n): recorrer todos los subconjuntos de n elementos
// (1 << n es 2^n; cada máscara representa un subconjunto)
for (int mascara = 0; mascara < (1 << n); mascara++) { /* ... */ }

De la restricción a un plan candidato

Las restricciones ayudan a evaluar una idea, pero no determinan la técnica. Para 2·10⁵ elementos, comparar todos los pares supone del orden de 4·10¹⁰ operaciones; ordenar y recorrer, del orden de unos millones. Es una razón para buscar un enfoque más eficiente, no una prueba de que ordenar resuelva la pregunta.

Valor máximo y cantidad de datos son variables distintas. Un solo número puede valer 10¹⁸. Probar divisores hasta su raíz requiere hasta 10⁹ iteraciones: O(√n) no vuelve pequeño ese trabajo. Una exponenciación rápida puede usar unas 60 iteraciones para un exponente de ese tamaño, pero resuelve otra pregunta; no reemplaza automáticamente una prueba de primalidad.

Suma todos los casos. Un algoritmo cuadrático para n = 3000 puede recorrer 9 millones de pares. Cien casos de ese tamaño elevarían el trabajo a 900 millones. Si el enunciado garantiza que la suma de n no supera 3000, la suma de los cuadrados no supera 9 millones: es una restricción distinta.

Con consultas, escribe el costo de preparar y de responder: construir prefijos y responder q sumas cuesta O(n+q); ordenar y hacer q búsquedas cuesta O(n log n + q log n). El número de consultas no decide por sí solo cuál corresponde. Aplica el mismo razonamiento a cada subtarea, donde una solución más sencilla puede ser suficiente.

El costo de tus herramientas (STL)

Un resumen para tenerlo a mano. La versión autoritativa —operación por operación, estructura por estructura, y generada desde los datos del vault— es el Catálogo de estructuras: si alguna vez estas dos no coinciden, manda esa.

OperaciónCosto
v.push_back(x)O(1) amortizado
sort(v.begin(), v.end())O(n log n)
set/map: insert, count, erase(clave)O(log n)
map: m[clave] (set no tiene [])O(log n)
priority_queue: push, popO(log n)
lower_bound en vector ordenadoO(log n)
unordered_set/unordered_mapO(1) promedio, O(n) peor caso
concatenar strings con s = s + tO(largo(s)+largo(t)) — ¡en un ciclo se vuelve O(n²)! (usa s += t)

Amortizado significa “caro a veces, barato en promedio garantizado”: n push_back cuestan O(n) en total aunque alguno realoque y copie todo. El análisis amortizado también justifica patrones como two pointers: cada puntero avanza a lo más n veces en total, aunque una iteración avance mucho.

Sobre unordered_*: útiles y legales, pero su O(1) es promedio — en Codeforces existen tests anti-hash que las degradan a O(n). Con set/map (O(log n) garantizado) nunca te llevas esa sorpresa. El Syllabus IOI además deja las tablas hash fuera del conocimiento exigido.

La memoria también cuenta

Lee el límite concreto del problema. En entornos habituales, int ocupa 4 bytes y long long, 8; puedes comprobarlo con sizeof. Estas cantidades usan MB decimales y cuentan solo los elementos:

  • Un vector de 10⁶ int: unos 4 MB.
  • Un vector de 10⁷ long long: unos 80 MB.
  • Una matriz de 3000² int: unos 36 MB; de long long, unos 72 MB.
  • Un vector de 10⁹ int: unos 4 GB, fuera de un límite de 256 MB.

Suma las estructuras que conviven, sus copias, el espacio reservado y la memoria del programa. Un vector de 80 MB puede caber en 256 MB; tres de ellos ya dejan poco margen. reserve no crea elementos y la capacidad puede superar el tamaño. La introducción está en 03 - Arreglos y búsqueda lineal y 04 - Matrices. Si no cabe, revisa si necesitas conservar todos los datos o puedes procesarlos al leerlos, comprimirlos o reutilizar espacio.

Trampas reales de TLE (con la complejidad “correcta”)

  • endl vacía el buffer en cada línea: usa "\n". Y parte main con ios::sync_with_stdio(false); cin.tie(nullptr);.
  • Pasar contenedores por copia: void f(vector<int> v) copia todo en cada llamada — pásalo por referencia (const vector<int>& v, ver Punteros y referencias).
  • Constantes grandes: map es O(log n) con constante pesada; si las llaves están en un rango pequeño, un vector de frecuencias evita buscar en un árbol y guarda datos contiguos. Estima también la memoria del rango completo.
  • Recursión profunda: el número de llamadas que cabe depende del tamaño de cada llamada y del límite de pila. Un camino largo puede causar stack overflow; la versión iterativa permite guardar la frontera explícitamente.

Ejemplo de análisis completo

“n ≤ 2·10⁵ precios y q ≤ 2·10⁵ consultas: ¿cuántos precios ≤ x?” Fuerza bruta: O(n·q) = 4·10¹⁰ ✗. Plan: sort O(n log n) + upper_bound por consulta O(log n) → total O((n+q) log n) del orden de 7·10⁶ operaciones de comparación: un candidato razonable, que todavía depende de la implementación y del límite. Ese razonamiento — costo total, no costo por línea — es el hábito que esta guía quiere instalar.

🧪 Autoevaluación

Di la complejidad de cada uno antes de abrir la respuesta.

for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) hacer_algo();
for (int i = 0; i < n; i++) sort(v.begin(), v.end());
for (int i = 1; i <= n / i; i++) hacer_algo();
for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++) hacer_algo();
set<int> s;
for (int i = 0; i < n; i++) s.insert(x[i]);

Relacionado: 07 - Cuánto se demora tu programa (introducción guiada) · Búsqueda Binaria · Progresión OCI a IOI · volver a Referencia. Para profundizar 🇬🇧: el capítulo Time Complexity de la USACO Guide.