Complejidad temporal

En los concursos de programación, el programa tiene que terminar de ejecutarse dentro de un plazo para recibir puntaje. En USACO, este límite es de $2$ segundos para envíos en C++ y de $4$ segundos para envíos en Java/Python. Una estimación conservadora de la cantidad de operaciones que el servidor del juez puede manejar por segundo es $10^8$, aunque podría acercarse a $5 \cdot 10^8$ si los factores constantes son buenos^{Si no se sabe qué son los factores constantes, no hay problema: los explicamos más abajo.}.

Cálculos de complejidad

Queremos un método para calcular cuántas operaciones hace falta para ejecutar cada algoritmo, en función del tamaño de la entrada $n$. Por suerte, esto se puede hacer con relativa facilidad usando la notación Big O , que expresa la complejidad temporal del peor caso como una función de $n$ cuando $n$ se vuelve arbitrariamente grande. La complejidad es una cota superior de la cantidad de pasos que requiere un algoritmo en función del tamaño de la entrada. En notación Big O, denotamos la complejidad de una función como $\mathcal{O}(f(n))$, donde en general se omiten los factores constantes y los términos de menor orden de $f(n)$. Veamos algunos ejemplos de cómo funciona, a continuación.

El código siguiente es $\mathcal{O}(1)$, porque ejecuta una cantidad constante de operaciones.

int a = 5;
int b = 7;
int c = 4;
int d = a + b + c + 153;

int a = 5;
int b = 7;
int c = 4;
int d = a + b + c + 153;

a = 5
b = 7
c = 4
d = a + b + c + 153

Las operaciones de entrada y salida también se asumen $\mathcal{O}(1)$. En los ejemplos siguientes, asumimos que el código dentro de los bucles es $\mathcal{O}(1)$.

La complejidad temporal de un bucle es la cantidad de iteraciones que ejecuta. Por ejemplo, los siguientes fragmentos son ambos $\mathcal{O}(n)$.

for (int i = 1; i <= n; i++) {
	// código de tiempo constante aquí
}

int i = 0;
while (i < n) {
	// código de tiempo constante aquí
	i++;
}

for (int i = 1; i <= n; i++) {
	// código de tiempo constante aquí
}

int i = 0;
while (i < n) {
	// código de tiempo constante aquí
	i++;
}

for i in range(1, n + 1):
	pass  # código de tiempo constante aquí

i = 0
while i < n:
	# código de tiempo constante aquí
	i += 1

Como ignoramos los factores constantes y los términos de menor orden, los siguientes ejemplos también son $\mathcal{O}(n)$:

for (int i = 1; i <= 5 * n + 17; i++) {
	// código de tiempo constante aquí
}

for (int i = 1; i <= n + 457737; i++) {
	// código de tiempo constante aquí
}

for (int i = 1; i <= 5 * n + 17; i++) {
	// código de tiempo constante aquí
}

for (int i = 1; i <= n + 457737; i++) {
	// código de tiempo constante aquí
}

for i in range(5 * n + 17):
	pass  # código de tiempo constante aquí
 
for i in range(n + 457737):
	pass  # código de tiempo constante aquí

La complejidad temporal de varios bucles se obtiene multiplicando las complejidades temporales de cada uno. Este ejemplo es $\mathcal{O}(nm)$, porque el bucle externo corre $\mathcal{O}(n)$ iteraciones y el interno $\mathcal{O}(m)$.

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
		// código de tiempo constante aquí
	}
}

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
		// código de tiempo constante aquí
	}
}

for i in range(n):
	for j in range(m):
		pass  # código de tiempo constante aquí

En este ejemplo, el bucle externo corre $\mathcal{O}(n)$ iteraciones, y el interno corre entre $1$ y $n$ iteraciones (como máximo $n$). Como la notación Big O calcula la complejidad temporal del peor caso, tratamos el bucle interno como un factor de $n$.^{También podemos hacer un poco de cuentas para calcular exactamente cuántas veces se ejecuta el código: 1+2+…+n = n*(n+1)/2 = (n^2 + n)/2 = O(n^2)} Así, este código es $\mathcal{O}(n^2)$.

for (int i = 1; i <= n; i++) {
	for (int j = i; j <= n; j++) {
		// código de tiempo constante aquí
	}
}

for (int i = 1; i <= n; i++) {
	for (int j = i; j <= n; j++) {
		// código de tiempo constante aquí
	}
}

for i in range(n):
	for j in range(i, n):
		pass  # código de tiempo constante aquí

Si un algoritmo tiene varios bloques, su complejidad temporal es la peor entre las de cada bloque. Por ejemplo, el código siguiente es $\mathcal{O}(n^2)$.

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		// código de tiempo constante aquí
	}
}
for (int i = 1; i <= n + 58834; i++) {
	// más código de tiempo constante aquí
}

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		// código de tiempo constante aquí
	}
}
for (int i = 1; i <= n + 58834; i++) {
	// más código de tiempo constante aquí
}

for i in range(n):
	for j in range(n):
		pass  # código de tiempo constante aquí
 
for i in range(n + 58834):
	pass  # más código de tiempo constante aquí

El código siguiente es $\mathcal{O}(n^2 + m)$, porque consiste en dos bloques de complejidad $\mathcal{O}(n^2)$ y $\mathcal{O}(m)$, y ninguno es una función de menor orden respecto de la otra.

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		// código de tiempo constante aquí
	}
}
for (int i = 1; i <= m; i++) {
	// más código de tiempo constante aquí
}

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		// código de tiempo constante aquí
	}
}
for (int i = 1; i <= m; i++) {
	// más código de tiempo constante aquí
}

for i in range(n):
	for j in range(n):
		pass  # código de tiempo constante aquí
 
for i in range(m):
	pass  # más código de tiempo constante aquí

Complejidades y restricciones comunes

Los factores de complejidad de algunos algoritmos y estructuras de datos comunes son los siguientes:

• Fórmulas matemáticas que solo calculan una respuesta: $\mathcal{O}(1)$
• Búsqueda binaria: $\mathcal{O}(\log n)$
• Conjunto/mapa ordenado o cola de prioridad: $\mathcal{O}(\log n)$ por operación
• Factorización en primos de un entero, o comprobar de forma naive si un entero es primo o compuesto: $\mathcal{O}(\sqrt{n})$
• Leer $n$ elementos de entrada: $\mathcal{O}(n)$
• Recorrer un arreglo o una lista de $n$ elementos: $\mathcal{O}(n)$
• Ordenamiento: normalmente $\mathcal{O}(n \log n)$ para los algoritmos de ordenamiento por defecto (mergesort, Collections.sort, Arrays.sort)
• Java Quicksort, función Arrays.sort sobre primitivos: $\mathcal{O}(n^2)$
  • Ver Introduction to Data Structures para más detalles.
• Recorrer todos los subconjuntos de tamaño $k$ de los elementos de entrada: $\mathcal{O}(n^k)$. Por ejemplo, recorrer todas las ternas es $\mathcal{O}(n^3)$.
• Recorrer todos los subconjuntos: $\mathcal{O}(2^n)$
• Recorrer todas las permutaciones: $\mathcal{O}(n!)$

Estas son cotas superiores conservadoras del valor de $n$ para cada complejidad temporal. A veces se puede con más, pero esto permite chequear rápido si un algoritmo es viable.

Factor constante

El factor constante refiere a que distintas operaciones con la misma complejidad tardan un poco distinto en ejecutarse. Por ejemplo, tres sumas tardan un poco más que una sola suma. Otro ejemplo: aunque la búsqueda binaria sobre un arreglo y la inserción en un conjunto ordenado son ambas $\mathcal{O}(\log n)$, la búsqueda binaria es notablemente más rápida.

El factor constante se ignora por completo en la notación Big O. La mayoría de las veces está bien, pero si el límite de tiempo es particularmente ajustado, se puede recibir límite de tiempo excedido (TLE) con la complejidad esperada. Cuando pasa eso, hay que tener en cuenta el factor constante. Por ejemplo, un código que recorre todas las ternas ordenadas en $\mathcal{O}(n^3)$ se puede acelerar por un factor de $6$ si solo hace falta recorrer las ternas no ordenadas.

Por ahora, no hay que preocuparse por optimizar los factores constantes: alcanza con tenerlos presentes.

Definición formal de la notación Big O

Sean $f$ y $g$ funciones no negativas de $\mathbb{R}_{\ge 0}$ a $\mathbb{R}_{\ge 0}$. Si existen constantes positivas $n_0$ y $c$ tales que $f(n) \le c \cdot g(n)$ siempre que $n \ge n_0$, decimos que $f(n) = \mathcal{O}(g(n))$.

Por lo tanto, podríamos decir que la complejidad temporal de una función lineal, $\mathcal{O}(n)$, también es $\mathcal{O}(n/2)$, $\mathcal{O}(2n)$, $\mathcal{O}(n^2)$, $\mathcal{O}(2^n)$, $\mathcal{O}(n^n)$, etc. Sin embargo, en general escribimos la función más simple entre las más restrictivas, que en el caso de la función lineal de arriba es $\mathcal{O}(n)$.

Cuestionario