# Complejidad algorítmica

Algoritmos y Estructuras de Datos (CB100) - FIUBA  
Martin Klöckner - [mklockner@fi.uba.ar](mailto:mklockner@fi.uba.ar)  

Se dice que un algorítmico es mas eficiente que otro si consume menos recursos,
o se ejecuta mas rápido. La eficiencia se puede medir en términos espaciales
(cantidad de memoria estática y dinámica que utiliza al ejecutarse) o en
términos temporales (el tiempo que tarda en ejecutarse) en general se busca una
relación de compromiso que comprende ambos factores.

Cuando se hace un análisis de la complejidad temporal de un algoritmo, se hace
referencia al tamaño de entrada del problema, o tamaño del problema, este tamaño
depende de la naturaleza del problema y corresponde a aquel o aquellos elementos
que produzcan, al crecer, un aumento en el tiempo de ejecución. Por ejemplo, al
calcular el factorial de un número, el tamaño del problema es el número al cual
se quiere calcular el factorial, ya que cuanto mayor sea este número mayor será
el tiempo de ejecución del algoritmo, otro ejemplo es el caso de una búsqueda
binaria en la cual el tamaño del problema será el tamaño del vector a ordenar.

Se denota entonces el coste real para una operación de $n$ entradas como $T(n)$,
esta coste mide el número de operaciones elementales requeridas para ejecutar el
algoritmo que se describe, y si bien al analizar un algoritmo existe un mejor
caso, un caso promedio y un peor caso, en la practica se suele definir a $T(n)$
en términos del peor caso, ya que determina cual sería el número de operaciones
elementales requeridas con la peor entrada posible. Por ejemplo en el siguiente
caso, la cantidad de ciclos ejecutados depende directamente de la posición del
dato en el vector, en el mejor caso es $1$ y es cuando el dato está en el primer
elemento, el caso promedio, es un promedio ponderado entre las probabilidades de
todas las posibles entradas, en este caso resulta $n/2$, el peor caso es cuando
está al final, y en ese caso la cantidad de operaciones elementales requeridas
es $n$, por esto ultimo la complejidad algorítmica $T(n)$ resulta $n$,
denotándose $T(n) = n$.

```c++
int get_pos(int* vec, int len, int data) {
    for(int pos = 0; pos < len; ++pos) {
        if(vec[i] == data) {
            return pos;
        }
    }
    return -1;
}
```

## Operaciones elementales

Las operaciones elementales son aquellas operaciones básicas de bajo nivel que
un algoritmo ejecuta y que tienen un costo constante (es decir, toman el mismo
tiempo, independientemente del tamaño de la entrada). Se considera operaciones
elementales a las operaciones aritméticas básicas (`+`, `-`, `*`, etc),
comparaciones lógicas (`==`, `!=`, `>`, etc), transferencias de control,
asignaciones a variables de tipos básicos (`x = 5`, `a = b`, etc), acceso a
memoria (`a[i]`, `x = b`, etc).

Las operaciones elementales sirven para independizar la definición de la
complejidad de un algoritmo de la maquina en la cual se ejecuta, ya que la
diferencia será una constante relacionada a la rapidez con la cual la maquina en
la cual se ejecuta el algoritmo puede realizar dichas operaciones elementales.

```c++
int a;      // 1 operación elemental
a = 5;      // 1 operación elemental
a = a + 5;  // 2 OE (acceso a memoria y suma) 
```

En el ejemplo anterior la complejidad algorítmica resulta $T(n) = 4$ y es
constante independiente de la entrada (no tiene entrada). En el ejemplo
siguiente la entrada es $n$.


```c++
int n;          // 1 operación elemental
std::cin >> n;  // se considera 1 OE

while(n > 0) {
    std::cout << n; // se considera 1 OE
    n--;            // 2 OE
}
```

El número total de operaciones elementales en el mejor de los casos es $2$ y es
cuando la entrada es $n <= 0$, en el peor de los caso se puede ver que el ciclo
`while` se ejecuta $n$ veces, resultando la complejidad algorítmica $T(n) = 2 +
n*3$.

En el siguiente ejemplo hay una condición y en una de las ramas un ciclo
`while`, ante estos casos se toma el peor caso, por lo tanto el coste total
resulta $T(n) = 4 + 3*n$, ya que es el coste del ciclo.

```c++
int n;          // 1 operacion elemental
std::cin >> n;  // 1 OE

if(n % 2 == 0) {     // 2 OE
    std::cout << n;  // 1 OE
} else {
    while(n > 0) {
        std::cout << n;  // 1 OE
        n--;             // 2 OE
    }
}
```

## Complejidad asintótica

La complejidad asintótica describe cómo crece el tiempo o espacio requerido por
un algoritmo cuando aumenta el tamaño de la entrada, ignorando constantes y
detalles menores. Esto se define debido a que en muchos casos calcular el costo
en operaciones elementales puede volverse tedioso, por lo que una mejor
aproximación es acotar apropiadamente el costo de ejecución del algoritmo. Por
ejemplo, se tiene el costo en función de la entrada de dos algoritmos $T_{1}(n)$
y $T_{2}(n)$:

$$T_{1}(n) = 3n^2 + 5n + 6\hspace{2em} T_{2}(n) = 12n^2 + 2$$

Se puede decir entonces, que ambos algoritmos tienen una complejidad similar en
términos de cotas, ya que para un número suficientemente grande de la entrada,
ambos algoritmos tienden a crecer de forma cuadrática.

Para acotar debidamente un algoritmo se definen 3 cotas, la cota superior, la
cota inferior y la cota mas ajustada o que aproxima mejor entre la cota
superior e inferior. 

### Cota inferior $\Omega$

La cota inferior (Omega $\Omega$) hace referencia a una función que acota
inferiormente al tiempo real $T(n)$ de un algoritmo dado, es decir, indica que
función será siempre superada por $T(n)$ para un $n$ suficientemente grande. 

### Cota que mejor aproxima $\Theta$

La cota que mejor aproxima (Theta $\Theta$) hace referencia a una funcion que
acota tanto inferiormente como superiormente al tiempo real $T(n)$ de un
algoritmo dado para un $n$ suficientemente grande.

### Cota superior $\mathcal{O}$

La cota superior hace referencia a una función que acota el crecimiento del
número de operaciones elementales o tiempo de ejecución de un algoritmo en el
**peor de los casos** para un número de entradas suficientemente grande, esto es
la minima función, ya que existen infinitas funciones que pueden ser mayores o
que pueden acotar el crecimiento de tiempo del algoritmo.

Por ejemplo para la siguiente función de tiempo real para un algoritmo dado
$T_{1}(n) = 3n^2 + 5n + 6$, se tiene que una cota superior es $O(n) = n^2$, ya
que para un número suficientemente grande el termino lineal y constante no hace
diferencia.

### Orden

El orden expresa el comportamiento dominante de un algoritmo para un número de
entradas $n$ suficientemente grande, en la practica se suele tomar como si fuera
la cota superior, aunque por definición no lo es. Por definición se dice que
$T(n)$ es de orden $g(n)$ (o pertenece a) $\mathcal{O}(g(n))$ si y solo si existen
constantes positivas $c$ y $n_{0}$, tales que se verifica para todo $n > n_{0}$
lo siguiente 

$$0 \leq T(n) \leq c*g(n)\hspace{1em} \forall n \geq n_{0}$$

En general en los casos en donde $T(n)$ se expresa como un polinomio, el orden
$\mathcal{O}$ del algoritmo, es el termino de mayor grado de $T(n)$

Los ordenes mas comunes entre diferentes algoritmos se pueden ordenar en forma
creciente en cuanto a complejidad algorítmica, esto permite comparar la
eficiencia entre los algoritmos:

\begin{align*}
\mathcal{O}(1) &\subset \mathcal{O}(\log n) \subset \mathcal{O}(n) \subset \mathcal{O}(n \log n) \\
&\subset \mathcal{O}(n^2) \subset \mathcal{O}(n^3) \subset \cdots \subset \mathcal{O}(2^n) \subset \mathcal{O}(n!)
\end{align*}

![Complejidades algorítmicas](./func_cmp.png)

#### Propiedades del orden

A continuación se muestran propiedades de la cota superior $\mathcal{O}(f)$

1. $f$ es $\mathcal{O}(f)$ entonces $f$ esta acotada por su orden
2. $\mathcal{O}(f)$ es $\mathcal{O}(g) \Rightarrow \mathcal{O}(f) \subset \mathcal{O}(g)$ y $\mathcal{O}(g) \subset \mathcal{O}(f)$
3. $\mathcal{O}(f) = \mathcal{O}(g)$ $\Leftrightarrow$ $f$ es $\mathcal{O}(g)$ y $g$ es
   $\mathcal{O}(f)$
4. Si $f$ es $\mathcal{O}(g)$ y $g$ es $\mathcal{O}(h)$ $\Rightarrow$ $f$ es $\mathcal{O}(h)$
5. Si $f$ es $\mathcal{O}(g)$ y $f$ es $\mathcal{O}(h)$ $\Rightarrow$ $f$ es $\mathcal{O}(min(g, h))$
6. Si $f_{1}$ es $\mathcal{O}(g)$ y $f_{2}$ es $\mathcal{O}(h)$
   $\Rightarrow$ $f_{1} + f_{2}$ es $\mathcal{O}(max(g, h))$
7. Si $f_{1}$ es $\mathcal{O}(g)$ y $f_{2}$ es $\mathcal{O}(h)$
   $\Rightarrow$ $f_{1} * f_{2}$ es $\mathcal{O}(g*h)$

## Algoritmos recursivos

Dado una función de costo real con recurrencia (es decir que depende de la misma
función para términos anteriors) por ejemplo $T(n) = T(n-1) + 1$ se puede hallar
la complejidad mediante dos métodos gentales, el primero el método de expansion,
en el cual se trata de un método iterativo evaluando como depende la función con
las iteraciones, y en el segundo método de resolución, aplicando el teorema
maestro, el cual es una formula general.

### Método de expansión

El método de expansion se trata de ir hallando los términos recursivos mediante
la formula del coste real $T(n)$ y reemplazando en si misma, es un proceso
iterativo. Por ejemplo se tiene una expresión de $T(n)$:

$$\begin{align}
T(n) = 2T\left(\frac{n}{2}\right) + \mathcal{O}(1)
\end{align}$$

De la ecuación anterior se puede obtener $T\left(\frac{n}{2}\right)$
reemplazando $n$ con $n/2$:

$$\begin{align}
T\left(\frac{n}{2}\right) = 2T\left(\frac{n}{4}\right) +
\mathcal{O}(1)
\end{align}$$

Por lo tanto reemplazando $(2)$ en $(1)$ resulta:

$$\begin{align}
T(n) &= 2\cdotp \left[2T\left(\frac{n}{4}\right) + \mathcal{O}(1)\right] + \mathcal{O}(1) \nonumber\\
     &= 4T\left(\frac{n}{4}\right) + 2\mathcal{O}(1) + \mathcal{O}(1) \nonumber\\
     &= 4T\left(\frac{n}{4}\right) + 3\mathcal{O}(1)
\end{align}$$

Pero de $(1)$ también se puede obtener $T\left(\frac{n}{4}\right)$:

$$\begin{align}
T\left(\frac{n}{4}\right) = 2T\left(\frac{n}{8}\right) + \mathcal{O}(1)
\end{align}$$

Y reemplazando $(4)$ en la ecuación $(3)$:

$$\begin{align}
T(n) &= 4\cdotp \left[2T\left(\frac{n}{8}\right) + \mathcal{O}(1)\right]  + 2\mathcal{O}(1) + \mathcal{O}(1) \nonumber\\
     &= 8T\left(\frac{n}{8}\right) + 4\mathcal{O}(1) + 2\mathcal{O}(1) + \mathcal{O}(1)\nonumber\\
     &= 8T\left(\frac{n}{8}\right) + 7\mathcal{O}(1)
\end{align}$$

Se puede ver que luego de realizar $k$ veces el mismo procedimiento resulta:

$$\begin{align}
T(n) = 2^{k}\cdotp T\left(\frac{n}{2^k}\right) + (2^{k}-1)\cdotp \mathcal{O}(1)
\end{align}$$

Pero las iteraciones se terminan cuando el numero de entradas es $1$, entonces
en $(6)$:

$$\begin{align}
\frac{n}{2^k} = 1 \Rightarrow n = 2^k \Rightarrow \boxed{log_{2}(n) = k}
\end{align}$$

Con $(7)$ en $(6)$ resulta

$$T(n) = n\cdotp T(1) + (n - 1)\cdotp \mathcal{O}(1)$$

De la expresión anterior, suponiendo $T(1) = \mathcal{O}(1)$ y aproximando, resulta

$$\begin{align*}
T(n) &= n\cdotp \mathcal{O}(1) + (n - 1)\cdotp \mathcal{O}(1) \\
     &= \mathcal{O}(n) + \mathcal{O}(n) \Rightarrow \boxed{T(n)     = \mathcal{O}(n)}
\end{align*}$$

Es decir la complejidad resulta $\mathcal{O}(n)$. El mismo problema se podría haber

### Teorema maestro

El teorema maestro se trata de una solución general para hallar la complejidad
dependiendo de como evolucionan los términos, en general se tienen dos forums,
la forma lineal, o por sustracción y la forma por division, las diferencias o
cuando aplicar cada una se muestran a continuación.

#### Reducción por sustracción

Dado una función de costo real $T(n)$ de la forma

$$T(n) = a\cdotp T(n-b)+\mathcal{O}(n^{k})$$

Entonces la complejidad algorítmica, o la solución de la ecuación de recurrencia
$T(n)$ resulta:

$$T(n) = 
\begin{cases}
\hspace{0.75em} \mathcal{O}(n^{(n/b)}\cdotp n^{k}) & \text{si } a > 1 \\
\hspace{0.75em} \mathcal{O}(n^{k+1})               & \text{si } a = 1 \\
\hspace{0.75em} \mathcal{O}(n^k)                   & \text{si } a < 1
\end{cases}$$

#### Reducción por division

Dado una función de costo real $T(n)$ de la forma

$$T(n) = 
\begin{cases}
\hspace{0.75em} c\cdotp n^{k}                                     & \text{si } 1 \leq n < b \\
\hspace{0.75em} a\cdotp T\left(\frac{n}{b}\right) + c\cdotp n^{k} & \text{si } n \geq b
\end{cases}$$

Entonces la complejidad algorítmica, o la solución de la ecuación de recurrencia
$T(n)$ resulta:

$$T(n) = 
\begin{cases}
\hspace{0.75em} \mathcal{O}(n^k)                & \text{si } a < b^{k} \\
\hspace{0.75em} \mathcal{O}(n^{k}\cdotp log(n)) & \text{si } a = b^{k} \\
\hspace{0.75em} \mathcal{O}(n^{log_{b}(a)})     & \text{si } a > b^{k}
\end{cases}$$

\vspace{-0.5em}

## Complejidad amortizada

Cuando se mide la complejidad de un algoritmo mediante el peor caso
($\mathcal{O}$) puede haber casos en los que no sea representativo, es decir, el
peor caso dista mucho de la media de ejecución del algoritmo, por lo que se usa
la **complejidad amortizada** la cual es una especie de promedio por operación
de un algoritmo en el peor de los casos a lo largo de una serie de operaciones. 

Por definición la complejidad amortizada es una técnica de análisis que se
utiliza para determinar el tiempo promedio por operación de un algoritmo en el
peor de los casos a lo largo de una secuencia de operaciones. En lugar de
analizar el tiempo proporciona una estimación del costo total de una serie de
operaciones, dividiendo este costo total por el numero de operaciones. Este tipo
de análisis es especialmente útil cuando ciertas operaciones pueden ser muy
costosas individualmente, pero esas operaciones costosas ocurren con poca
frecuencia.

Existen varios métodos para realizar un análisis amortizado, pero el mas común
es calcular el costo total de una secuencia de operaciones y dividir por el
numero total de operaciones:

$$\boxed{\text{Costo amortizado } = \frac{T(n)}{n}}$$