Análisis de complejidad

Complejidad computacional #

La complejidad computacional nos permite analizar qué tan eficiente es un algoritmo, ya sea en espacio o tiempo de ejecución. Saber analizar la complejidad de los algoritmos que escribimos es vital en programación competitiva porque nos permite predecir si una solución corre bajo el tiempo límite antes de programarla.

No analizar la complejidad de una solución antes de programarla es un error, ya que es posible que ésta no sea lo suficientemente eficiente y perderemos tiempo valioso programando algo que dará Time Limit Exceeded (TLE).

En programación competitiva el análisis suele hacerse sobre el tiempo de ejecución y no sobre la memoria. Esto se debe a que los límites de memoria suelen ser más generosos y además la memoria está muy relacionada con el tiempo: crear $O(n)$ variables toma $O(n)$ tiempo. Por esto, casi siempre hablaremos de tiempo de ejecución, o simplemente tiempo.

La O grande #

La notación de O grande es por lejos la más usada en programación competitiva, ya que establece una cota superior para la cantidad de operaciones que nuestro algoritmo realiza. Nos interesa esta cota superior ya que los jueces y casos de prueba están diseñados para siempre poner a prueba nuestro código con el peor caso posible.

Existe una definición rigurosa con límites, pero para nuestro objetivo basta con entenderlo intuitivamente:

Con asintótico nos referimos, dicho de manera informal, a cuando $n$ es muy grande. En la práctica esto significa que $O(n^2 + n)$ es lo mismo que $O(n^2)$, dado que el término $n$ es despreciable al lado de $n^2$ cuando $n$ es muy grande. En programación competitiva trabajamos con números muy grandes, así que en la práctica esto es útil y simplifica el análisis: al final solo nos interesa el término dominante en la función. De la misma forma, las constantes que acompañan la función son despreciables: $O(3n^3 + 5n^2 + 5)$ es simplemente $O(n^3)$.

¿Operaciones? #

El análisis de complejidad toma alguna unidad primitiva para calcular la función $f(n)$ en $O(f(n))$. Podríamos hilar fino y expresar esto en función de la cantidad de bits que operamos o en ciclos del reloj de la CPU, pero en programación competitiva esto resulta innecesario y es suficiente con expresar la complejidad en función del tamaño de la entrada del problema que estamos resolviendo.

Diremos que las siguientes operaciones toman tiempo constante $O(1)$:

• Operaciones aritméticas, de bits y comparaciones: Esto incluye sumar, restar, dividir, multiplicar, el operador módulo, los operadores de bits y las comparaciones (<, >, <=, >=, ==). Aunque en la práctica dividir toma muchos más ciclos de reloj en la CPU que sumar, para nosotros esa diferencia será despreciable.
• Acceder y modificar memoria: Esto incluye leer una posición de un vector, declarar o asignar una variable primitiva.
• Otros: llamar una función, retornar un valor, leer o imprimir una variable a la consola y castear un tipo.

En teoría cualquier operación que no dependa del tamaño de la entrada de nuestro problema será $O(1)$. Cuando el tiempo límite de un problema está muy apretado puede ser útil saber cuáles de ellas son más lentas o más rápidas, pero la primera prioridad al proponer una solución es siempre el análisis asintótico.

Ejemplos #

Los siguientes ejemplos sirven para que practiques el análisis de complejidad. Recomendamos que intentes analizarla antes de ver la solución.

Suma de un arreglo #

int n;
cin >> n;
vector <int> arr(n);
for(int i=0; i<n; i++){
    cin >> arr[i];
}
int suma = 0;
for(int i=0; i<n; i++){
    suma += arr[i];
}
cout << suma << endl;

For anidado #

int n, m;
cin >> n >> m;
int res = 0;
for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
        res += i*j;
    }
}
cout << res << endl;

Par o imprimir #

int w;
cin >> w;
if(w%2 == 0){
    cout << "Es par" << endl;
}
else{
    for(int i=0; i<w; i++){
        cout << i << endl;
    }
}

Exponenciación #

int n;
cin >> n;
for(int i=0; i<n; i++){
    int j = 1;
    while(j<n){
        j *= 2;
    }
}

Índices #

int n;
cin >> n;
vector <int> arr(n);
vector <vector <int>> indices(n);
for(int i=0; i<n; i++){
    // en este problema leemos n números que están entre 0 y n-1.
    // Es decir, nos garantizan 0 <= arr[i] < n.
    cin >> arr[i];
    indices[arr[i]].push_back(i);
}

for(int x=0; x<n; x++){
    int suma = 0;
    for(int j=0; j<indices[x].size(); j++){
        suma += indices[x][j];
    }
    cout << suma << endl;
}

Serie harmónica #

int n;
cin >> n;
int ans = 0;
for (int i = 1; i < n; i++) {
  for (int j = 1; j < n; j += i) {
    ans += i*j;
  }
}

¿Cómo se si mi solución pasa en tiempo? #

Hay una regla de oro que sirve para estimar el tiempo de ejecución:

Como los tiempos límite suelen ser de alrededor de un segundo, esto significa que queremos realizar a lo más $10^8$ operaciones. Esto significa que si $n <= 10^4$, una solución $O(n^2)$ pasa justo en tiempo, pues $(10^4)^2 = 10^8$, mientras que una $O(n^3)$ dará TLE.

A continuación mostramos complejidades comunes que pasan en tiempo para varios tamaños posibles de entrada:

Problemas para ejercitar #

Es difícil encontrar problemas para ejercitar el análisis de complejidad, ya que se usa en todos los problemas. Estos problemas requieren un análisis de complejidad novedoso o más complicado de lo usual.

• Weird Algorithm - CSES
• Fun - Codeforces
• Meet in the Middle - CSES