chapter02.tex

\chapter{Complejidad temporal}

\index{complejidad temporal}

La eficiencia de los algoritmos es importante en la programación competitiva.
Usualmente, es fácil diseñar un algoritmo
que resuelva el problema lentamente,
pero el verdadero desafío es inventar un
algoritmo rápido.
Si el algoritmo es demasiado lento, solo obtendrá
puntos parciales o no obtendrá puntos en absoluto.

La \key{complejidad temporal} de un algoritmo
estima cuánto tiempo utilizará el algoritmo
para una determinada entrada.
La idea es representar la eficiencia
como una función cuyo parámetro es el tamaño de la entrada.
Al calcular la complejidad temporal,
podemos averiguar si el algoritmo es lo suficientemente rápido
sin implementarlo.

\section{Reglas de cálculo}

La complejidad temporal de un algoritmo
se denota $O(\cdots)$
donde los tres puntos representan alguna
función.
Usualmente, la variable $n$ denota
el tamaño de la entrada.
Por ejemplo, si la entrada es un arreglo de números,
$n$ será el tamaño del arreglo,
y si la entrada es una cadena,
$n$ será la longitud de la cadena.

\subsubsection*{Bucles}

Una razón común por la cual un algoritmo es lento es
que contiene muchos bucles que recorren la entrada.
Cuantos más bucles anidados contenga el algoritmo,
más lento será.
Si hay $k$ bucles anidados,
la complejidad temporal es $O(n^k)$.

Por ejemplo, la complejidad temporal del siguiente código es $O(n)$:
\begin{lstlisting}
for (int i = 1; i <= n; i++) {
    // codigo
}
\end{lstlisting}

Y la complejidad temporal del siguiente código es $O(n^2)$:
\begin{lstlisting}
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        // codigo
    }
}
\end{lstlisting}

\subsubsection*{Orden de magnitud}

Una complejidad temporal no nos dice el número exacto
de veces que se ejecuta el código dentro de un bucle,
sino que solo muestra el orden de magnitud.
En los siguientes ejemplos, el código dentro del bucle
se ejecuta $3n$, $n+5$ y $\lceil n/2 \rceil$ veces,
pero la complejidad temporal de cada código es $O(n)$.

\begin{lstlisting}
for (int i = 1; i <= 3*n; i++) {
    // codigo
}
\end{lstlisting}

\begin{lstlisting}
for (int i = 1; i <= n+5; i++) {
    // codigo
}
\end{lstlisting}

\begin{lstlisting}
for (int i = 1; i <= n; i += 2) {
    // codigo
}
\end{lstlisting}

Como otro ejemplo,
la complejidad temporal del siguiente código es $O(n^2)$:

\begin{lstlisting}
for (int i = 1; i <= n; i++) {
    for (int j = i+1; j <= n; j++) {
        // codigo
    }
}
\end{lstlisting}

\subsubsection*{Fases}

Si el algoritmo consiste en fases consecutivas,
la complejidad temporal total es la mayor
complejidad temporal de una sola fase.
La razón de esto es que la fase más lenta
usualmente es el cuello de botella del código.

Por ejemplo, el siguiente código consiste
en tres fases con complejidades temporales
$O(n)$, $O(n^2)$ y $O(n)$.
Por lo tanto, la complejidad temporal total es $O(n^2)$.

\begin{lstlisting}
for (int i = 1; i <= n; i++) {
    // codigo
}
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        // codigo
    }
}
for (int i = 1; i <= n; i++) {
    // codigo
}
\end{lstlisting}

\subsubsection*{Varias variables}

A veces, la complejidad temporal depende de
varios factores.
En este caso, la fórmula de la complejidad temporal
contiene varias variables.

Por ejemplo, la complejidad temporal del
siguiente código es $O(nm)$:

\begin{lstlisting}
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        // codigo
    }
}
\end{lstlisting}

\subsubsection*{Recursión}

La complejidad temporal de una función recursiva
depende del número de veces que se llama a la función
y de la complejidad temporal de una sola llamada.
La complejidad temporal total es el producto de
estos valores.

Por ejemplo, considera la siguiente función:
\begin{lstlisting}
void f(int n) {
    if (n == 1) return;
    f(n-1);
}
\end{lstlisting}
La llamada $\texttt{f}(n)$ provoca $n$ llamadas a la función,
y la complejidad temporal de cada llamada es $O(1)$.
Por lo tanto, la complejidad temporal total es $O(n)$.

Como otro ejemplo, considera la siguiente función:
\begin{lstlisting}
void g(int n) {
    if (n == 1) return;
    g(n-1);
    g(n-1);
}
\end{lstlisting}
En este caso, cada llamada a la función genera dos otras
llamadas, excepto para $n=1$.
Veamos qué pasa cuando se llama a $g$
con el parámetro $n$.
La siguiente tabla muestra las llamadas a la función
producidas por esta única llamada:
\begin{center}
\begin{tabular}{rr}
llamada a la función & número de llamadas \\
\hline
$g(n)$ & 1 \\
$g(n-1)$ & 2 \\
$g(n-2)$ & 4 \\
$\cdots$ & $\cdots$ \\
$g(1)$ & $2^{n-1}$ \\
\end{tabular}
\end{center}
Basado en esto, la complejidad temporal es
\[1+2+4+\cdots+2^{n-1} = 2^n-1 = O(2^n).\]

\section{Clases de complejidad}

\index{complexity classes}

La siguiente lista contiene complejidades temporales comunes
de algoritmos:

\begin{description}
\item[$O(1)$]
\index{constant-time algorithm}
El tiempo de ejecución de un algoritmo de \key{tiempo constante}
no depende del tamaño de la entrada.
Un algoritmo típico de tiempo constante es una fórmula directa
que calcula la respuesta.

\item[$O(\log n)$]
\index{logarithmic algorithm}
Un algoritmo \key{logarítmico} a menudo divide a la mitad
el tamaño de la entrada en cada paso.
El tiempo de ejecución de dicho algoritmo
es logarítmico, porque
$\log_2 n$ es igual al número de veces
que $n$ debe dividirse por 2 para obtener 1.

\item[$O(\sqrt n)$]
Un algoritmo de \key{raíz cuadrada} es más lento que
$O(\log n)$ pero más rápido que $O(n)$.
Una propiedad especial de las raíces cuadradas es que
$\sqrt n = n/\sqrt n$, por lo que la raíz cuadrada $\sqrt n$ se encuentra,
en cierto sentido, en el medio de la entrada.

\item[$O(n)$]
\index{linear algorithm}
Un algoritmo \key{lineal} recorre la entrada
un número constante de veces.
Esta suele ser la mejor complejidad temporal posible,
porque generalmente es necesario acceder a cada
elemento de entrada al menos una vez antes de
informar la respuesta.

\item[$O(n \log n)$]
Esta complejidad temporal a menudo indica que
el algoritmo ordena la entrada,
porque la complejidad temporal de los algoritmos de ordenación eficientes es $O(n \log n)$.
Otra posibilidad es que el algoritmo
use una estructura de datos donde cada operación
toma tiempo $O(\log n)$.

\item[$O(n^2)$]
\index{quadratic algorithm}
Un algoritmo \key{cuadrático} a menudo contiene
dos bucles anidados.
Es posible recorrer todos los pares de
elementos de entrada en tiempo $O(n^2)$.

\item[$O(n^3)$]
\index{cubic algorithm}
Un algoritmo \key{cúbico} a menudo contiene
tres bucles anidados.
Es posible recorrer todas las tripletas de
elementos de entrada en tiempo $O(n^3)$.

\item[$O(2^n)$]
Esta complejidad temporal a menudo indica que
el algoritmo itera a través de todos
los subconjuntos de los elementos de entrada.
Por ejemplo, los subconjuntos de $\{1,2,3\}$ son
$\emptyset$, $\{1\}$, $\{2\}$, $\{3\}$, $\{1,2\}$,
$\{1,3\}$, $\{2,3\}$ y $\{1,2,3\}$.

\item[$O(n!)$]
Esta complejidad temporal a menudo indica que
el algoritmo itera a través de todas
las permutaciones de los elementos de entrada.
Por ejemplo, las permutaciones de $\{1,2,3\}$ son
$(1,2,3)$, $(1,3,2)$, $(2,1,3)$, $(2,3,1)$,
$(3,1,2)$ y $(3,2,1)$.

\end{description}

\index{polynomial algorithm}
Un algoritmo es \key{polinomial}
si su complejidad temporal es a lo sumo $O(n^k)$
donde $k$ es una constante.
Todas las complejidades temporales anteriores excepto
$O(2^n)$ y $O(n!)$ son polinomiales.
En la práctica, la constante $k$ suele ser pequeña,
y por lo tanto, una complejidad temporal polinomial
significa aproximadamente que el algoritmo es \emph{eficiente}.

\index{NP-hard problem}

La mayoría de los algoritmos en este libro son polinomiales.
Sin embargo, hay muchos problemas importantes para los cuales
no se conoce ningún algoritmo polinomial, es decir,
nadie sabe cómo resolverlos de manera eficiente.
Los problemas \key{NP-hard} son un conjunto importante
de problemas para los cuales no se conoce ningún algoritmo polinomial\footnote{Un libro clásico sobre el tema es
\emph{Computers and Intractability: A Guide to the Theory
of NP-Completeness} de M. R. Garey y D. S. Johnson \cite{gar79}.}.

\section{Estimación de eficiencia}

Al calcular la complejidad temporal de un algoritmo,
es posible verificar, antes de implementarlo,
si es lo suficientemente eficiente para el problema.
El punto de partida para las estimaciones es el hecho de que
una computadora moderna puede realizar cientos de millones de
operaciones en un segundo.

Por ejemplo, supongamos que el límite de tiempo para
un problema es de un segundo y el tamaño de entrada es $n=10^5$.
Si la complejidad temporal es $O(n^2)$,
el algoritmo realizará aproximadamente $(10^5)^2=10^{10}$ operaciones.
Esto debería tomar al menos varias decenas de segundos,
por lo que el algoritmo parece ser demasiado lento para resolver el problema.

Por otro lado, dado el tamaño de entrada,
podemos intentar \emph{adivinar}
la complejidad temporal requerida por el algoritmo
que resuelve el problema.
La siguiente tabla contiene algunas estimaciones útiles
suponiendo un límite de tiempo de un segundo.

\begin{center}
\begin{tabular}{ll}
tamaño de entrada & complejidad temporal requerida \\
\hline
$n \le 10$ & $O(n!)$ \\
$n \le 20$ & $O(2^n)$ \\
$n \le 500$ & $O(n^3)$ \\
$n \le 5000$ & $O(n^2)$ \\
$n \le 10^6$ & $O(n \log n)$ o $O(n)$ \\
$n$ es grande & $O(1)$ o $O(\log n)$ \\
\end{tabular}
\end{center}

Por ejemplo, si el tamaño de entrada es $n=10^5$,
probablemente se espera que la complejidad temporal
del algoritmo sea $O(n)$ o $O(n \log n)$.
Esta información facilita el diseño del algoritmo,
porque descarta enfoques que producirían
un algoritmo con una peor complejidad temporal.

\index{constant factor}

Aún así, es importante recordar que la
complejidad temporal es solo una estimación de eficiencia,
porque oculta los \emph{factores constantes}.
Por ejemplo, un algoritmo que se ejecuta en tiempo $O(n)$
puede realizar $n/2$ o $5n$ operaciones.
Esto tiene un efecto importante en el tiempo real
de ejecución del algoritmo.

\section{Suma máxima de subarreglo}

\index{maximum subarray sum}

A menudo existen varios algoritmos posibles
para resolver un problema de manera que sus
complejidades temporales sean diferentes.
Esta sección discute un problema clásico que
tiene una solución directa de $O(n^3)$.
Sin embargo, al diseñar un algoritmo mejor,
es posible resolver el problema en tiempo $O(n^2)$
e incluso en tiempo $O(n)$.

Dado un arreglo de $n$ números,
nuestra tarea es calcular la
\key{suma máxima de subarreglo}, es decir,
la suma más grande posible de
una secuencia de valores consecutivos
en el arreglo\footnote{El libro de J. Bentley \emph{Programming Pearls} \cite{ben86} popularizó el problema.}.
El problema es interesante cuando puede haber
valores negativos en el arreglo.
Por ejemplo, en el arreglo
\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw (0,0) grid (8,1);

\node at (0.5,0.5) {$-1$};
\node at (1.5,0.5) {$2$};
\node at (2.5,0.5) {$4$};
\node at (3.5,0.5) {$-3$};
\node at (4.5,0.5) {$5$};
\node at (5.5,0.5) {$2$};
\node at (6.5,0.5) {$-5$};
\node at (7.5,0.5) {$2$};
\end{tikzpicture}
\end{center}
una subarreglo siguiente produce la suma máxima $10$:
\begin{center}
\begin{tikzpicture}[scale=0.7]
\fill[color=lightgray] (1,0) rectangle (6,1);
\draw (0,0) grid (8,1);

\node at (0.5,0.5) {$-1$};
\node at (1.5,0.5) {$2$};
\node at (2.5,0.5) {$4$};
\node at (3.5,0.5) {$-3$};
\node at (4.5,0.5) {$5$};
\node at (5.5,0.5) {$2$};
\node at (6.5,0.5) {$-5$};
\node at (7.5,0.5) {$2$};
\end{tikzpicture}
\end{center}

Suponemos que se permite un subarreglo vacío,
por lo que la suma máxima de subarreglo siempre es al menos $0$.

\subsubsection{Algoritmo 1}

Una manera directa de resolver el problema
es recorrer todos los subarreglos posibles,
calcular la suma de los valores en cada subarreglo y mantener
la suma máxima.
El siguiente código implementa este algoritmo:

\begin{lstlisting}
int mejor = 0;
for (int a = 0; a < n; a++) {
    for (int b = a; b < n; b++) {
        int suma = 0;
        for (int k = a; k <= b; k++) {
            suma += array[k];
        }
        mejor = max(mejor, suma);
    }
}
cout << mejor << "\n";
\end{lstlisting}

Las variables \texttt{a} y \texttt{b} fijan el primer y
último índice del subarreglo,
y se calcula la suma de los valores en la variable \texttt{suma}.
La variable \texttt{mejor} contiene la suma máxima encontrada durante la búsqueda.

La complejidad temporal del algoritmo es $O(n^3)$,
porque consiste en tres bucles anidados
que recorren la entrada.

\subsubsection{Algoritmo 2}

Es fácil hacer que el Algoritmo 1 sea más eficiente
eliminando uno de sus bucles.
Esto es posible al calcular la suma al mismo tiempo
que el extremo derecho del subarreglo se mueve.
El resultado es el siguiente código:

\begin{lstlisting}
int mejor = 0;
for (int a = 0; a < n; a++) {
    int suma = 0;
    for (int b = a; b < n; b++) {
        suma += array[b];
        mejor = max(mejor, suma);
    }
}
cout << mejor << "\n";
\end{lstlisting}
Después de este cambio, la complejidad temporal es $O(n^2)$.

\subsubsection{Algoritmo 3}

Sorprendentemente, es posible resolver el problema
en tiempo $O(n)$\footnote{En \cite{ben86}, este algoritmo lineal
se atribuye a J. B. Kadane, y a veces se
llama \index{Kadane's algorithm} \key{algoritmo de Kadane}.}, lo que significa
que solo un bucle es suficiente.
La idea es calcular, para cada posición del arreglo,
la suma máxima de un subarreglo que termina en esa posición.
Luego, la respuesta para el problema es el
máximo de esas sumas.

Consideremos el subproblema de encontrar la suma máxima del subarreglo
que termina en la posición $k$.
Existen dos posibilidades:
\begin{enumerate}
\item El subarreglo contiene solo el elemento en la posición $k$.
\item El subarreglo consiste en un subarreglo que termina
en la posición $k-1$, seguido por el elemento en la posición $k$.
\end{enumerate}

En el segundo caso, dado que queremos
encontrar un subarreglo con la suma máxima,
el subarreglo que termina en la posición $k-1$
también debería tener la suma máxima.
Así, podemos resolver el problema eficientemente
calculando la suma máxima del subarreglo
para cada posición final de izquierda a derecha.

El siguiente código implementa el algoritmo:
\begin{lstlisting}
int mejor = 0, suma = 0;
for (int k = 0; k < n; k++) {
    suma = max(array[k], suma + array[k]);
    mejor = max(mejor, suma);
}
cout << mejor << "\n";
\end{lstlisting}

El algoritmo contiene solo un bucle
que recorre la entrada,
por lo que la complejidad temporal es $O(n)$.
Esta también es la mejor complejidad temporal posible,
porque cualquier algoritmo para el problema
debe examinar todos los elementos del arreglo al menos una vez.

\subsubsection{Comparación de eficiencia}

Es interesante estudiar cuán eficientes son
los algoritmos en la práctica.
La siguiente tabla muestra los tiempos de ejecución
de los algoritmos anteriores para diferentes
valores de $n$ en una computadora moderna.

En cada prueba, la entrada se generó de forma aleatoria.
El tiempo necesario para leer la entrada no se midió.

\begin{center}
\begin{tabular}{rrrr}
tamaño del arreglo $n$ & Algoritmo 1 & Algoritmo 2 & Algoritmo 3 \\
\hline
$10^2$ & $0.0$ s & $0.0$ s & $0.0$ s \\
$10^3$ & $0.1$ s & $0.0$ s & $0.0$ s \\
$10^4$ & > $10.0$ s & $0.1$ s & $0.0$ s \\
$10^5$ & > $10.0$ s & $5.3$ s & $0.0$ s \\
$10^6$ & > $10.0$ s & > $10.0$ s & $0.0$ s \\
$10^7$ & > $10.0$ s & > $10.0$ s & $0.0$ s \\
\end{tabular}
\end{center}

La comparación muestra que todos los algoritmos
son eficientes cuando el tamaño de entrada es pequeño,
pero tamaños de entrada más grandes muestran diferencias
notables en los tiempos de ejecución de los algoritmos.
El Algoritmo 1 se vuelve lento
cuando $n=10^4$, y el Algoritmo 2
se vuelve lento cuando $n=10^5$.
Solo el Algoritmo 3 es capaz de procesar
incluso las entradas más grandes instantáneamente.