Complejidad Computacional

Objetivo

Desarrollar intuición para mapear situaciones a $O (n)$ , $O (lo g n)$ , $O (1)$

Prerequisitos

Notación big O

Recorrido

Cotas
¿Cuáles de estas afirmaciones son verdaderas? Recordá: la consigna asume que se busca una cota ajustada, no la más grande posible.

$n \in O (1)$

Ver respuesta

Falso. $O (1)$ significa tiempo constante. $n$ crece sin límite, no puede estar acotada por una constante. Para cota ajustada, $n \in O (n)$ .

$500 \in O (n)$

Ver respuesta

Verdadero pero no es cota ajustada. $500$ es constante, así que $500 \in O (1)$ . Decir $O (n)$ es correcto matemáticamente ( $500 \leq c \cdot n$ para todo $n \geq 1$ con $c = 500$ ), pero no es ajustado.

$4 n \in O (4^{n})$

Ver respuesta

Falso como cota ajustada. $4 n$ crece linealmente, no exponencialmente. La cota ajustada es $O (n)$ , no $O (4^{n})$ . $O (4^{n})$ sería una cota correcta pero muy holgada.

$n^{2} + \frac{1}{5} n^{3} \in O (n^{3})$

Ver respuesta

Verdadero. El término dominante es $n^{3}$ . $n^{2} + \frac{1}{5} n^{3} \leq c \cdot n^{3}$ para $c = 1$ y $n \geq 1$ . Como el término dominante es exactamente $n^{3}$ , $O (n^{3})$ es además la cota ajustada.

$n \cdot (n + 2)^{2/3} \in O (n^{2})$

Ver respuesta

Falso como cota ajustada. $n \cdot (n + 2)^{2/3} \approx n^{1 + 2/3} = n^{5/3}$ . La cota ajustada es $O (n^{5/3})$ , no $O (n^{2})$ . $O (n^{2})$ sería válida pero no ajustada.

$2 \cdot lo g_{2} n \in O (lo g_{4} n)$

Ver respuesta

Verdadero. $lo g_{4} n = \frac{l o g _{2} n}{l o g _{2} 4} = \frac{l o g _{2} n}{2}$ . Entonces $2 \cdot lo g_{2} n = 4 \cdot lo g_{4} n$ . Son proporcionales: ambos crecen igual de rápido. $O (lo g n)$ es la misma clase sin importar la base.

$3^{n} \in O (2^{n})$

Ver respuesta

Falso. $3^{n} / 2^{n} = (3/2)^{n} \to \infty$ . Es decir, $3^{n}$ crece mucho más rápido que $2^{n}$ , no puede estar acotada por ella. $O (3^{n}) \neq \subset O (2^{n})$ .

Enlace al original
La mesa más cercana
Imaginá que sos el dueño de un restaurante y tenés que encontrar la mesa libre más cercana a la entrada. Tenés tres estrategias:
- Estrategia A: revisás cada mesa una por una desde adelante.
- Estrategia B: dividís el salón a la mitad, descartás mitades hasta encontrarla.
- Estrategia C: cada mozo memorizó qué mesas están libres en su zona y te avisa al instante.
¿A qué complejidades $O (f (n))$ corresponden A, B y C? Justificá brevemente.
Enlace al original
Saludos
Llegás a una reunión. La regla es que cada persona saluda a todas las demás exactamente una vez.

Con 2 personas: 1 saludo. Con 3 personas: 3 saludos. Con 4 personas: 6 saludos. Con 5 personas: 10 saludos.

¿Ves el patrón? Cada persona nueva tiene que saludar a todas las anteriores.
1. Si hay n personas ¿cuántos saludos habrá en total?
2. Si hay 100 personas en la reunión, ¿cuántos saludos hay?
Enlace al original
Doblando un papel
Tomás una hoja y la doblás a la mitad. Ahora tiene el doble de grosor. La doblás de nuevo: cuatro veces el grosor original. Cada doblez duplica el grosor.

Empezás con 0,1 mm de grosor.

Después de 10 dobleces: ~100 mm (10 cm). Después de 20 dobleces: ~100 metros. Después de 30 dobleces: ~100 km. Después de 42 dobleces: llegarías a la Luna.

Esto es crecimiento exponencial: la función $2^{n}$ . Ahora pensalo al revés. Si el papel ya tiene 1024 capas y querés saber cuántos dobleces se hicieron, ¿cuánto trabajo te lleva calcularlo?
Enlace al original
Ajedrez
Historia

El rey Iadava, obligado por la guerra, vence al invasor Varangul en una sangrienta batalla, pero el triunfo le cuesta la vida de su hijo, el príncipe Adjamir. Consumido por el dolor, el monarca cae en una obsesión enfermiza, reviviendo una y otra vez la batalla, incapaz de superar su pérdida pese a las oraciones de los brahmanes.
Un joven brahmán llamado Lahur Sessa se presenta ante el rey con un juego que ha inventado para aliviar su tristeza: el ajedrez. A través de sus reglas y simbolismos, Sessa le enseña que la fuerza de un rey depende de sus súbditos y que, en la guerra, el sacrificio de algunas piezas puede ser necesario para alcanzar la victoria. El juego ayuda a Iadava a comprender y aceptar lo ocurrido en la batalla.
Agradecido, el rey ofrece a Sessa cualquier recompensa, y este pide granos de trigo que se dupliquen en cada casilla del tablero. Aunque parece una petición humilde, el cálculo revela una cantidad imposible de pagar. Sessa renuncia entonces a su recompensa y deja una lección sobre la prudencia y los límites del poder. Impresionado por su sabiduría, el rey lo nombra su primer ministro.

Tomado de: El hombre que calculaba, de Malba Tahan. Resumido sin piedad por la IA.

Enunciado

El brahmán Lahur Sessa pide como recompensa granos de trigo colocados sobre un tablero de ajedrez de 64 casillas, de la siguiente manera:
- En la primera casilla, 1 grano.
- En la segunda, 2 granos.
- En la tercera, 4 granos.
- Y así sucesivamente, duplicando la cantidad en cada casilla.
1. ¿Cuántos granos hay en la casilla $n$ ?
2. ¿Cuántos granos hay en total en el tablero?
3. Expresá ambas respuestas usando notación matemática.
4. ¿A qué orden de complejidad $O (f (n))$ corresponde el crecimiento de la cantidad de granos?
Enlace al original
Análisis de Fragmento de Código 1
Mirá este fragmento de código:
```
PARA i = 1 HASTA n HACER
  PARA j = i HASTA n HACER
    suma ← suma + 1
FIN PARA
```
¿Cuál es la complejidad de este código? ¿Por qué?
Enlace al original

Análisis de Fragmento de Código 2
Mirá este fragmento de código:
Leer(a)
n ← a * a
c ← 0

MIENTRAS (a > 1) HACER
    a ← a / 2
    PARA i = 1 HASTA n HACER
        c ← c * 2
    FIN PARA
FIN MIENTRAS
¿Cuál es la complejidad de este código? ¿Por qué?
Enlace al original

Análisis de Fragmento de Código 3
Mirá este fragmento de código:
PARA i = 2 HASTA n HACER
    k ← i
    PARA k = i HASTA 2 (paso -1) HACER
        SI a(k-1) > a(k) ENTONCES
            Aux ← a(k-1)
            a(k-1) ← a(k)
            a(k) ← Aux
        FIN SI
    FIN PARA
FIN PARA
¿Cuál es la complejidad de este código? ¿Por qué?
Enlace al original

Factorial Recursivo e Iterativo
Ambas versiones de este algoritmo calculan $n!$ , pero ¿tienen la misma complejidad?

Versión iterativa:
```
PARA i = 1 HASTA n HACER
  result ← result × i
return result
```
Versión recursiva:
```
SI n = 0
  return 1
SI NO
  return factorial(n-1) × n
```
Ambas hacen exactamente $n$ multiplicaciones. Pero la versión recursiva tiene overhead de stack: cada llamada guarda el estado en memoria.

¿Cuál es la complejidad temporal y espacial de cada una?
Enlace al original
Nociones de Complejidad
Si tenés 1 segundo para correr tu algoritmo y una PC1 que hace $1 0^{6}$ ops/seg, ¿cuántos elementos podés procesar con cada complejidad? ¿Y en una computadora PC2 que es 1000 veces más rápida que PC1?

Confeccionemos esta tabla:

Complejidad Elementos (PC1) Elementos (PC2)
$O (1)$
$O (lo g n)$
$O (n)$
$O (n lo g n)$
$O (n^{2})$
$O (2^{n})$
Enlace al original
Cálculo de Complejidad 1
Si se sabe que el algoritmo de selección tardó 10 segundos en ordenar 10000 elementos:
1. ¿Cuántos elementos podría ordenar en el triple de tiempo?
2. ¿Cuánto tardaría en ordenar el triple de elementos?
3. ¿Cuánto tardaría en ordenar el triple de elementos en una máquina 3 veces más rápida?
Ver solución

Solución paso a paso

Este tipo de ejercicios requiere, casi siempre, de un análisis de la situación inicial. No siempre se tienen todos los datos, y es mejor tenerlos a mano antes de comenzar a responder las preguntas.

Marquemos la información disponible:
se sabe que el algoritmo de selección tardó 10 segundos en ordenar 10000 elementos

Esa información nos permite llenar varias partes de la ecuación:
$T (n) = c \cdot O (f (n))$
Sabemos que:
- $T (n)$ es 10 segundos (dato)
- $f (n)$ es $n^{2}$ (por complejidad de Selección)
- $n$ es $1 0^{4}$ (dato. Recomendamos notación científica)
Entonces podemos armar la ecuación en la situación original, y despejar $c_{0}$ :
$T_{0} (n) 1010 \frac{10}{1 0 ^{8}} 1 0^{- 7} = c_{0} \cdot n_{0}^{2} = c_{0} \cdot (1 0^{4})^{2} = c_{0} \cdot 1 0^{8} = c_{0} = c_{0}$
Con este dato, la constante computacional de la computadora inicial, podemos empezar a responder las preguntas:

1. ¿Cuántos elementos podría ordenar en el triple de tiempo?

Esta situación requiere despejar la ecuación, con el nuevo $T_{1} = 3 \cdot T_{0}$

Sabemos que:
- $T_{1}$ es $3 \cdot T_{0}$
- $f_{1} (n)$ es $n^{2}$ (mismo algoritmo)
- $c_{1}$ es $1 0^{- 7}$ (misma computadora)
- $n_{1}$ es la incógnita
A priori podemos deducir que, si el mismo algoritmo se ejecuta por más tiempo, debe procesar una entrada mayor necesariamente. Por ello, $n_{1} > n_{0}$

Despejemos:
$T_{1} (n) 30 30 \cdot 1 0^{7} 3 \cdot 1 0^{8} 3 \cdot 1 0^{8} 3 \cdot 1 0^{4} 17320 = c_{1} \cdot n_{1}^{2} = 1 0^{- 7} \cdot n_{1}^{2} = n_{1}^{2} = n_{1}^{2} = n_{1} = n_{1} = n_{1}$
Es notable que se debe redondear hacia abajo, ya que no se puede ordenar “una fracción de elemento”, y ya que no se pudo ordenar, sería inapropiado redondear hacia arriba.

La parte más importante es preguntarnos… ¿tiene sentido este resultado? En este caso, sí lo tiene: un algoritmo cuadrático, triplicando el tiempo, implica que el tamaño se multiplicó por raiz de tres.

2. ¿Cuánto tardaría en ordenar el triple de elementos?

En esta nueva situación, volvemos a referirnos al contexto original, y $n_{2} = 3 \cdot n_{0}$

Sabemos que:
- $n_{2}$ es $3 \cdot n_{0}$ (dato)
- $f_{2} (n)$ es $n^{2}$ (mismo algoritmo)
- $c_{2}$ es $1 0^{- 7}$ (misma computadora)
- $T_{2}$ es la incógnita
A priori podemos deducir que, si el mismo algoritmo se ejecuta para más elementos, debe tardar más. Habiendo visto los resultados del punto anterior, parecería que debe tardar 9 veces más (3 al cuadrado). Entonces, seguramente $T_{2} > T_{0}$

Resolvamos:
$T_{2} (n) T_{2} (n) T_{2} (n) T_{2} (n) T_{2} (n) T_{2} (n) = c_{2} \cdot n_{2}^{2} = 1 0^{- 7} \cdot (3 \cdot 1 0^{4})^{2} = 1 0^{- 7} \cdot 9 \cdot 1 0^{8} = 9 \cdot 1 0^{- 7} \cdot 1 0^{8} = 9 \cdot 1 0^{1} = 90$
Volvemos a preguntarnos si tiene sentido el resultado. En este caso, pudimos predecir el valor simplemente realizando un análisis a priori de la situación: efectivamente $T_{2} = 3^{2} \cdot T_{0}$ .

3. ¿Cuánto tardaría en ordenar el triple de elementos en una máquina 3 veces más rápida?

Esta última situación nos plantea un cambio en el valor de $c_{0}$ . La pregunta será… ¿al ser más rápida, el valor debe ser más grande o más pequeño al original? Para no depender de nuestra memoria, analizamos la ecuación original:
$T (n) = c \cdot O (f (n))$
Y deducimos: la $c$ está en el término de la derecha. Una computadora más rápida debería hacer que el $T (n)$ baje, aún manteniendo inalteradas las otras variables. Es por ello que necesitaríamos que se achique el valor de $c$ . En conclusión: una computadora más rápida implica un $c$ más pequeño.

Adicionalmente, podemos pensar que el tiempo debe ser menor que el del punto anterior, que tiene la situación similar a la actual.

Dicho esto, sabemos que:
- $n_{3}$ es $3 \cdot 1 0^{4}$ (triple de elementos)
- $f_{3} (n)$ es $n^{2}$ (mismo algoritmo)
- $c_{3}$ es $\frac{1 0 ^{- 7}}{3}$ (computadora “tres veces más rápida”)
- $T_{3}$ es la incógnita
Resolvamos:
$T_{3} (n) T_{3} (n) T_{3} (n) T_{3} (n) T_{3} (n) T_{3} (n) = c_{3} \cdot n_{3}^{2} = \frac{1 0 ^{- 7}}{3} \cdot (3 \cdot 1 0^{4})^{2} = \frac{1 0 ^{- 7}}{3} \cdot 3^{2} \cdot 1 0^{8} = \frac{3 ^{2} \cdot 1 0 ^{- 7} \cdot 1 0 ^{8}}{3} = \frac{3 ^{2}}{3} \cdot 10 = 30$
Preguntémonos por última vez si tiene sentido el resultado. En este caso, si la computadora es tres veces más rápida, deberíamos confirmar que $T_{3} = \frac{T _{2}}{3}$ , y efectivamente es el resultado obtenido.
Enlace al original
Cálculo de Complejidad 2
Suponga que debe ordenar un vector por el método de Selección. Su entrada es de 2000 elementos y en su PC obtuvo un tiempo de 10 segundos.
1. Si debiera ordenar un vector de 5000 entradas, ¿cuál sería el tiempo estimado de ejecución?
2. ¿Cuál sería el tamaño máximo de vector que podría ordenar en 40 segundos?
3. Resuelva este problema reemplazando el método de ordenamiento por cada uno de los métodos vistos.
Enlace al original
Cálculo de Complejidad 3
El algoritmo de selección ordenó un vector de 10000 enteros en 5 seg.
1. ¿Cuál será el tamaño del vector que espera ordenar en 20 seg.? Justifique.
2. ¿Qué sucede si ordena ambos vectores en una máquina 5 veces más rápida?
Enlace al original
Cálculo de Complejidad 4
Utilizando el algoritmo de inserción se ordenó en un tiempo $T_{1}$ , $N_{1}$ elementos. En un tiempo de $2 \cdot T_{1}$ se ordenó un vector de $2 \cdot N_{1}$ elementos.

Explique las condiciones bajo las cuales pudieron hacerse las pruebas.
Enlace al original
Cálculo de Complejidad 5
Utilizando el algoritmo de QuickSort se ordenó un vector de 1 millón de elementos en un tiempo $T_{1}$ . ¿Cuántos elementos espera ordenar en un tiempo $2 \cdot T_{1}$ ?
Enlace al original
El detective algorítmico
Un programador midió su algoritmo con distintas entradas:
```
n = 100 → 0.01 seg
n = 200 → 0.04 seg
n = 400 → 0.16 seg
n = 800 → 0.64 seg
```
Cada vez que duplica n, el tiempo se multiplica por 4.
1. ¿Qué complejidad tiene este algoritmo?
2. ¿Podés deducirlo solo con los datos? Justificá tu respuesta.
Enlace al original

Arcana

Explorador

Complejidad Computacional

Objetivo

Prerequisitos

Recorrido

Cotas

La mesa más cercana

Saludos

Doblando un papel

Ajedrez

Historia

Enunciado

Análisis de Fragmento de Código 1

Análisis de Fragmento de Código 2

Análisis de Fragmento de Código 3

Factorial Recursivo e Iterativo

Nociones de Complejidad

Cálculo de Complejidad 1

Solución paso a paso

1. ¿Cuántos elementos podría ordenar en el triple de tiempo?

2. ¿Cuánto tardaría en ordenar el triple de elementos?

3. ¿Cuánto tardaría en ordenar el triple de elementos en una máquina 3 veces más rápida?

Cálculo de Complejidad 2

Cálculo de Complejidad 3

Cálculo de Complejidad 4

Cálculo de Complejidad 5

El detective algorítmico

Vista Gráfica

Tabla de Contenidos

Retroenlaces

Complejidad	Elementos (PC1)	Elementos (PC2)
$O (1)$
$O (lo g n)$
$O (n)$
$O (n lo g n)$
$O (n^{2})$
$O (2^{n})$