chapter04.tex

\chapter{Estructuras de datos}

\index{estructura de datos}

Una \key{estructura de datos} es una forma de almacenar
datos en la memoria de una computadora.
Es importante elegir una estructura de datos apropiada
para un problema,
porque cada estructura de datos tiene sus propias
ventajas y desventajas.
La pregunta crucial es: ¿qué operaciones
son eficientes en la estructura de datos elegida?

Este capítulo presenta las estructuras de datos más importantes
en la biblioteca estándar de C++.
Es una buena idea usar la biblioteca estándar
siempre que sea posible,
porque ahorrará mucho tiempo.
Más adelante en el libro, aprenderemos sobre estructuras de datos más sofisticadas
que no están disponibles
en la biblioteca estándar.

\section{Arreglos dinámicos}

\index{arreglo dinámico}
\index{vector}

Un \key{arreglo dinámico} es un arreglo cuyo
tamaño se puede cambiar durante la ejecución
del programa.
El arreglo dinámico más popular en C++ es
la estructura \texttt{vector},
que se puede usar casi como un arreglo ordinario.

El siguiente código crea un vector vacío y
agrega tres elementos a él:

\begin{lstlisting}
vector<int> v;
v.push_back(3); // [3]
v.push_back(2); // [3,2]
v.push_back(5); // [3,2,5]
\end{lstlisting}

Después de esto, los elementos se pueden acceder como en un arreglo ordinario:

\begin{lstlisting}
cout << v[0] << "\n"; // 3
cout << v[1] << "\n"; // 2
cout << v[2] << "\n"; // 5
\end{lstlisting}

La función \texttt{size} devuelve el número de elementos en el vector.
El siguiente código itera a través
del vector e imprime todos los elementos en él:

\begin{lstlisting}
for (int i = 0; i < v.size(); i++) {
    cout << v[i] << "\n";
}
\end{lstlisting}

\begin{samepage}
Una forma más corta de iterar a través de un vector es la siguiente:

\begin{lstlisting}
for (auto x : v) {
    cout << x << "\n";
}
\end{lstlisting}
\end{samepage}

La función \texttt{back} devuelve el último elemento
en el vector, y
la función \texttt{pop\_back} elimina el último elemento:

\begin{lstlisting}
vector<int> v;
v.push_back(5);
v.push_back(2);
cout << v.back() << "\n"; // 2
v.pop_back();
cout << v.back() << "\n"; // 5
\end{lstlisting}

El siguiente código crea un vector con cinco elementos:

\begin{lstlisting}
vector<int> v = {2,4,2,5,1};
\end{lstlisting}

Otra forma de crear un vector es dar el número
de elementos y el valor inicial para cada elemento:

\begin{lstlisting}
// tamano 10, valor inicial 0
vector<int> v(10);
\end{lstlisting}
\begin{lstlisting}
// tamano 10, valor inicial 5
vector<int> v(10, 5);
\end{lstlisting}

La implementación interna de un vector
utiliza un arreglo ordinario.
Si el tamaño del vector aumenta y
el arreglo se vuelve demasiado pequeño,
se asigna un nuevo arreglo y todos los
elementos se mueven al nuevo arreglo.
Sin embargo, esto no sucede a menudo y el
tiempo de complejidad promedio de
\texttt{push\_back} es $O(1)$.

\index{cadena}

La estructura \texttt{string}
también es un arreglo dinámico que se puede usar casi como un vector.
Además, hay una sintaxis especial para cadenas
que no está disponible en otras estructuras de datos.
Las cadenas se pueden combinar usando el símbolo \texttt{+}.
La función $\texttt{substr}(k,x)$ devuelve la subcadena
que comienza en la posición $k$ y tiene longitud $x$,
y la función $\texttt{find}(\texttt{t})$ encuentra la posición
de la primera aparición de una subcadena \texttt{t}.

El siguiente código presenta algunas operaciones de cadena:

\begin{lstlisting}
string a = "hatti";
string b = a+a;
cout << b << "\n"; // hattihatti
b[5] = 'v';
cout << b << "\n"; // hattivatti
string c = b.substr(3,4);
cout << c << "\n"; // tiva
\end{lstlisting}

\section{Estructuras de conjunto}

\index{conjunto}

Un \key{conjunto} es una estructura de datos que
mantiene una colección de elementos.
Las operaciones básicas de los conjuntos son la inserción de elementos, la búsqueda y la eliminación.

La biblioteca estándar de C++ contiene dos implementaciones de conjunto:
La estructura \texttt{set} se basa en un árbol binario equilibrado
y sus operaciones funcionan en tiempo $O(\log n)$.
La estructura \texttt{unordered\_set} usa hashing,
y sus operaciones funcionan en tiempo $O(1)$ en promedio.

La elección de qué implementación de conjunto usar
es a menudo una cuestión de gusto.
El beneficio de la estructura \texttt{set}
es que mantiene el orden de los elementos
y proporciona funciones que no están disponibles
en \texttt{unordered\_set}.
Por otro lado, \texttt{unordered\_set}
puede ser más eficiente.

El siguiente código crea un conjunto
que contiene enteros,
y muestra algunas de las operaciones.
La función \texttt{insert} agrega un elemento al conjunto,
la función \texttt{count} devuelve el número de ocurrencias
de un elemento en el conjunto,
y la función \texttt{erase} elimina un elemento del conjunto.

\begin{lstlisting}
set<int> s;
s.insert(3);
s.insert(2);
s.insert(5);
cout << s.count(3) << "\n"; // 1
cout << s.count(4) << "\n"; // 0
s.erase(3);
s.insert(4);
cout << s.count(3) << "\n"; // 0
cout << s.count(4) << "\n"; // 1
\end{lstlisting}


Un conjunto se puede usar principalmente como un vector,
pero no es posible acceder
a los elementos usando la notación \texttt{[]}.
El siguiente código crea un conjunto,
imprime el número de elementos en él, y luego
itera a través de todos los elementos:
\begin{lstlisting}
set<int> s = {2,5,6,8};
cout << s.size() << "\n"; // 4
for (auto x : s) {
    cout << x << "\n";
}
\end{lstlisting}

Una propiedad importante de los conjuntos es
que todos sus elementos son \emph{distintos}.
Por lo tanto, la función \texttt{count} siempre devuelve
ya sea 0 (el elemento no está en el conjunto)
o 1 (el elemento está en el conjunto),
y la función \texttt{insert} nunca agrega
un elemento al conjunto si ya está
ahí.
El siguiente código ilustra esto:

\begin{lstlisting}
set<int> s;
s.insert(5);
s.insert(5);
s.insert(5);
cout << s.count(5) << "\n"; // 1
\end{lstlisting}

C++ también contiene las estructuras
\texttt{multiset} y \texttt{unordered\_multiset}
que de otra manera funcionan como \texttt{set}
y \texttt{unordered\_set}
pero pueden contener múltiples instancias de un elemento.
Por ejemplo, en el siguiente código todas las tres instancias
del número 5 se agregan a un multiset:

\begin{lstlisting}
multiset<int> s;
s.insert(5);
s.insert(5);
s.insert(5);
cout << s.count(5) << "\n"; // 3
\end{lstlisting}
La función \texttt{erase} elimina
todas las instancias de un elemento
de un multiset:
\begin{lstlisting}
s.erase(5);
cout << s.count(5) << "\n"; // 0
\end{lstlisting}
A menudo, solo se debe eliminar una instancia,
lo que se puede hacer de la siguiente manera:
\begin{lstlisting}
s.erase(s.find(5));
cout << s.count(5) << "\n"; // 2
\end{lstlisting}

\section{Estructuras de mapa}

\index{map}

Un \key{mapa} es una matriz generalizada
que consta de pares clave-valor.
Si bien las claves en una matriz ordinaria son siempre
los enteros consecutivos $0,1,\ldots,n-1$,
donde $n$ es el tamaño de la matriz,
las claves en un mapa pueden ser de cualquier tipo de datos y
no tienen que ser valores consecutivos.

La biblioteca estándar de C++ contiene dos mapas
implementaciones que corresponden al conjunto
implementaciones: la estructura
\texttt{map} se basa en un balanceado
árbol binario y acceder a elementos
toma $O(\log n)$ tiempo,
mientras que la estructura
\texttt{unordered\_map} usa hashing
y acceder a elementos toma $O(1)$ tiempo en promedio.

El siguiente código crea un mapa
donde las claves son cadenas y los valores son enteros:

\begin{lstlisting}
map<string,int> m;
m["monkey"] = 4;
m["banana"] = 3;
m["harpsichord"] = 9;
cout << m["banana"] << "\n"; // 3
\end{lstlisting}

Si se solicita el valor de una clave
pero el mapa no lo contiene,
la clave se agrega automáticamente al mapa con
un valor predeterminado.
Por ejemplo, en el siguiente código,
la clave ''aybabtu'' con valor 0
se agrega al mapa.

\begin{lstlisting}
map<string,int> m;
cout << m["aybabtu"] << "\n"; // 0
\end{lstlisting}
La función \texttt{count} comprueba
si una clave existe en un mapa:
\begin{lstlisting}
if (m.count("aybabtu")) {
    // clave existe
}
\end{lstlisting}
El siguiente código imprime todas las claves y valores
en un mapa:
\begin{lstlisting}
for (auto x : m) {
    cout << x.first << " " << x.second << "\n";
}
\end{lstlisting}

\section{Iteradores y rangos}

\index{iterator}

Muchas funciones en la biblioteca estándar de C++
operan con iteradores.
Un \key{iterador} es una variable que apunta
a un elemento en una estructura de datos.

Los iteradores que se usan a menudo \texttt{begin}
y \texttt{end} definen un rango que contiene
todos los elementos en una estructura de datos.
El iterador \texttt{begin} apunta a
el primer elemento en la estructura de datos,
y el iterador \texttt{end} apunta a
la posición \emph{después} del último elemento.
La situación se ve de la siguiente manera:

\begin{center}
\begin{tabular}{llllllllll}
\{ & 3, & 4, & 6, & 8, & 12, & 13, & 14, & 17 & \} \\
& $\uparrow$ & & & & & & & & $\uparrow$ \\
& \multicolumn{3}{l}{\texttt{s.begin()}} & & & & & & \texttt{s.end()} \\
\end{tabular}
\end{center}

Tenga en cuenta la asimetría en los iteradores:
\texttt{s.begin()} apunta a un elemento en la estructura de datos,
mientras que \texttt{s.end()} apunta fuera de la estructura de datos.
Por lo tanto, el rango definido por los iteradores es \emph{semiabierto}.

\subsubsection{Trabajando con rangos}

Los iteradores se utilizan en las funciones de la biblioteca estándar de C++
que reciben un rango de elementos en una estructura de datos.
Por lo general, queremos procesar todos los elementos en un
estructura de datos, por lo que los iteradores
\texttt{begin} y \texttt{end} se dan para la función.

Por ejemplo, el siguiente código ordena un vector
usando la función \texttt{sort},
luego invierte el orden de los elementos usando la función
\texttt{reverse}, y finalmente baraja el orden de
los elementos usando la función \texttt{random\_shuffle}.

\index{sort@\texttt{sort}}
\index{reverse@\texttt{reverse}}
\index{random\_shuffle@\texttt{random\_shuffle}}

\begin{lstlisting}
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
random_shuffle(v.begin(), v.end());
\end{lstlisting}

Estas funciones también se pueden usar con una matriz ordinaria.
En este caso, las funciones reciben punteros a la matriz
en lugar de iteradores:

\newpage
\begin{lstlisting}
sort(a, a+n);
reverse(a, a+n);
random_shuffle(a, a+n);
\end{lstlisting}

\subsubsection{Iteradores de conjunto}

Los iteradores se utilizan a menudo para acceder a los elementos de un conjunto.
El siguiente código crea un iterador
\texttt{it} que apunta al elemento más pequeño de un conjunto:
\begin{lstlisting}
set<int>::iterator it = s.begin();
\end{lstlisting}
Una forma más corta de escribir el código es la siguiente:
\begin{lstlisting}
auto it = s.begin();
\end{lstlisting}
El elemento al que apunta un iterador
se puede acceder utilizando el símbolo \texttt{*}.
Por ejemplo, el siguiente código imprime
el primer elemento del conjunto:

\begin{lstlisting}
auto it = s.begin();
cout << *it << "\n";
\end{lstlisting}

Los iteradores se pueden mover utilizando los operadores
\texttt{++} (hacia adelante) y \texttt{--} (hacia atrás),
lo que significa que el iterador se mueve al siguiente
o elemento anterior del conjunto.

El siguiente código imprime todos los elementos
en orden creciente:
\begin{lstlisting}
for (auto it = s.begin(); it != s.end(); it++) {
    cout << *it << "\n";
}
\end{lstlisting}
El siguiente código imprime el elemento más grande del conjunto:
\begin{lstlisting}
auto it = s.end(); it--;
cout << *it << "\n";
\end{lstlisting}

La función $\texttt{find}(x)$ devuelve un iterador
que apunta a un elemento cuyo valor es $x$.
Sin embargo, si el conjunto no contiene $x$,
el iterador será \texttt{end}.

\begin{lstlisting}
auto it = s.find(x);
if (it == s.end()) {
    // x no se encuentra
}
\end{lstlisting}

La función $\texttt{lower\_bound}(x)$ devuelve
un iterador al elemento más pequeño del conjunto
cuyo valor es \emph{al menos} $x$, y
la función $\texttt{upper\_bound}(x)$
devuelve un iterador al elemento más pequeño del conjunto
cuyo valor es \emph{mayor que} $x$.
En ambas funciones, si no existe tal elemento,
el valor de retorno es \texttt{end}.
Estas funciones no son compatibles con
la estructura \texttt{unordered\_set} que
no mantiene el orden de los elementos.

\begin{samepage}
Por ejemplo, el siguiente código encuentra el elemento
más cercano a $x$:

\begin{lstlisting}
auto it = s.lower_bound(x);
if (it == s.begin()) {
    cout << *it << "\n";
} else if (it == s.end()) {
    it--;
    cout << *it << "\n";
} else {
    int a = *it; it--;
    int b = *it;
    if (x-b < a-x) cout << b << "\n";
    else cout << a << "\n";
}
\end{lstlisting}

El código asume que el conjunto no está vacío,
y recorre todos los casos posibles
utilizando un iterador \texttt{it}.
Primero, el iterador apunta al elemento más pequeño
cuyo valor es al menos $x$.
Si \texttt{it} es igual a \texttt{begin},
el elemento correspondiente está más cerca de $x$.
Si \texttt{it} es igual a \texttt{end},
el elemento más grande del conjunto está más cerca de $x$.
Si ninguno de los casos anteriores se cumple,
el elemento más cercano a $x$ es o bien el
elemento que corresponde a \texttt{it} o el elemento anterior.
\end{samepage}

\section{Otras estructuras}

\subsubsection{Bitset}

\index{bitset}

Un \key{bitset} es una matriz
cuyo valor de cada elemento es 0 o 1.
Por ejemplo, el siguiente código crea
un bitset que contiene 10 elementos:
\begin{lstlisting}
bitset<10> s;
s[1] = 1;
s[3] = 1;
s[4] = 1;
s[7] = 1;
cout << s[4] << "\n"; // 1
cout << s[5] << "\n"; // 0
\end{lstlisting}

La ventaja de usar bitsets es que
requieren menos memoria que las matrices ordinarias,
porque cada elemento de un bitset solo
utiliza un bit de memoria.
Por ejemplo, 
si se almacenan $n$ bits en una matriz \texttt{int},
se utilizarán $32n$ bits de memoria,
pero un bitset correspondiente solo requiere $n$ bits de memoria.
Además, los valores de un bitset
se pueden manipular de manera eficiente utilizando
operadores bit a bit, lo que permite
optimizar algoritmos utilizando bitsets.

El siguiente código muestra otra forma de crear el bitset anterior:
\begin{lstlisting}
bitset<10> s(string("0010011010")); // de derecha a izquierda
cout << s[4] << "\n"; // 1
cout << s[5] << "\n"; // 0
\end{lstlisting}

La función \texttt{count} devuelve el número
de unos en el bitset:

\begin{lstlisting}
bitset<10> s(string("0010011010"));
cout << s.count() << "\n"; // 4
\end{lstlisting}

El siguiente código muestra ejemplos de uso de operaciones bit a bit:
\begin{lstlisting}
bitset<10> a(string("0010110110"));
bitset<10> b(string("1011011000"));
cout << (a&b) << "\n"; // 0010010000
cout << (a|b) << "\n"; // 1011111110
cout << (a^b) << "\n"; // 1001101110
\end{lstlisting}

\subsubsection{Deque}

\index{deque}

Un \key{deque} es una matriz dinámica
cuyo tamaño se puede cambiar de forma eficiente
en ambos extremos de la matriz.
Al igual que un vector, un deque proporciona las funciones
\texttt{push\_back} y \texttt{pop\_back}, pero
también incluye las funciones
\texttt{push\_front} y \texttt{pop\_front}
que no están disponibles en un vector.

Un deque se puede utilizar de la siguiente manera:
\begin{lstlisting}
deque<int> d;
d.push_back(5); // [5]
d.push_back(2); // [5,2]
d.push_front(3); // [3,5,2]
d.pop_back(); // [3,5]
d.pop_front(); // [5]
\end{lstlisting}



La implementación interna de una cola de doble extremo
es más compleja que la de un vector,
y por esta razón, una cola de doble extremo es más lenta que un vector.
Aun así, tanto agregar como eliminar
elementos toma $O(1)$ tiempo en promedio en ambos extremos.

\subsubsection{Pila}

\index{pila}

Una \key{pila}
es una estructura de datos que proporciona dos
operaciones de tiempo $O(1)$:
agregar un elemento a la cima,
y eliminar un elemento de la cima.
Solo es posible acceder al elemento superior
de una pila.

El siguiente código muestra cómo se puede usar una pila:
\begin{lstlisting}
stack<int> s;
s.push(3);
s.push(2);
s.push(5);
cout << s.top(); // 5
s.pop();
cout << s.top(); // 2
\end{lstlisting}
\subsubsection{Cola}

\index{cola}

Una \key{cola} también
proporciona dos operaciones de tiempo $O(1)$:
agregar un elemento al final de la cola,
y eliminar el primer elemento de la cola.
Solo es posible acceder al primero
y al último elemento de una cola.

El siguiente código muestra cómo se puede usar una cola:
\begin{lstlisting}
queue<int> q;
q.push(3);
q.push(2);
q.push(5);
cout << q.front(); // 3
q.pop();
cout << q.front(); // 2
\end{lstlisting}

\subsubsection{Cola de prioridad}

\index{cola de prioridad}
\index{montículo}

Una \key{cola de prioridad}
mantiene un conjunto de elementos.
Las operaciones compatibles son la inserción y,
dependiendo del tipo de la cola,
la recuperación y la eliminación de
ya sea el elemento mínimo o máximo.
La inserción y la eliminación toman $O(\log n)$ tiempo,
y la recuperación toma $O(1)$ tiempo.

Si bien un conjunto ordenado admite de manera eficiente
todas las operaciones de una cola de prioridad,
la ventaja de usar una cola de prioridad es
que tiene factores constantes más pequeños.
Una cola de prioridad generalmente se implementa utilizando
una estructura de montón que es mucho más simple que un
árbol binario equilibrado utilizado en un conjunto ordenado.

\begin{samepage}
De forma predeterminada, los elementos de una cola de prioridad de C++
están ordenados en orden decreciente,
y es posible encontrar y eliminar el
elemento más grande en la cola.
El siguiente código ilustra esto:

\begin{lstlisting}
priority_queue<int> q;
q.push(3);
q.push(5);
q.push(7);
q.push(2);
cout << q.top() << "\n"; // 7
q.pop();
cout << q.top() << "\n"; // 5
q.pop();
q.push(6);
cout << q.top() << "\n"; // 6
q.pop();
\end{lstlisting}
\end{samepage}

Si queremos crear una cola de prioridad
que admita la búsqueda y la eliminación
del elemento más pequeño,
podemos hacerlo de la siguiente manera:

\begin{lstlisting}
priority_queue<int,vector<int>,greater<int>> q;
\end{lstlisting}

\subsubsection{Estructuras de datos basadas en políticas}

El compilador \texttt{g++} también admite
algunas estructuras de datos que no son parte
de la biblioteca estándar de C++.
Tales estructuras se llaman estructuras de datos \emph{basadas en políticas}.
Para usar estas estructuras, las siguientes líneas
deben agregarse al código:
\begin{lstlisting}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds; 
\end{lstlisting}
Después de esto, podemos definir una estructura de datos \texttt{indexed\_set} que
es como \texttt{set} pero se puede indexar como una matriz.
La definición para valores \texttt{int} es la siguiente:
\begin{lstlisting}
typedef tree<int,null_type,less<int>,rb_tree_tag,
             tree_order_statistics_node_update> indexed_set; 
\end{lstlisting}
Ahora podemos crear un conjunto de la siguiente manera:
\begin{lstlisting}
indexed_set s;
s.insert(2);
s.insert(3);
s.insert(7);
s.insert(9);
\end{lstlisting}
La especialidad de este conjunto es que tenemos acceso a
los índices que los elementos tendrían en una matriz ordenada.
La función $\texttt{find\_by\_order}$ devuelve
un iterador al elemento en una posición dada:
\begin{lstlisting}
auto x = s.find_by_order(2);
cout << *x << "\n"; // 7
\end{lstlisting}
Y la función $\texttt{order\_of\_key}$
devuelve la posición de un elemento dado:
\begin{lstlisting}
cout << s.order_of_key(7) << "\n"; // 2
\end{lstlisting}
Si el elemento no aparece en el conjunto,
obtenemos la posición que el elemento tendría
en el conjunto:
\begin{lstlisting}
cout << s.order_of_key(6) << "\n"; // 2
cout << s.order_of_key(8) << "\n"; // 3
\end{lstlisting}
Ambas funciones funcionan en tiempo logarítmico.

\section{Comparación con la clasificación}

A menudo es posible resolver un problema
utilizando estructuras de datos o clasificación.
A veces hay diferencias notables
en la eficiencia real de estos enfoques,
que pueden estar ocultas en sus complejidades de tiempo.

Consideremos un problema donde
se nos dan dos listas $A$ y $B$
que ambas contienen $n$ elementos.
Nuestra tarea es calcular el número de elementos
que pertenecen a ambas listas.
Por ejemplo, para las listas
\[A = [5,2,8,9] \hspace{10px} \textrm{y} \hspace{10px} B = [3,2,9,5],\]
la respuesta es 3 porque los números 2, 5
y 9 pertenecen a ambas listas.

Una solución sencilla al problema es
recorrer todos los pares de elementos en $O(n^2)$ tiempo,
pero a continuación nos centraremos en
algoritmos más eficientes.

\subsubsection{Algoritmo 1}
Construimos un conjunto de los elementos que aparecen en $A$,
y después de esto, iteramos a través de los elementos
de $B$ y verificamos para cada elemento si también
pertenece a $A$.
Esto es eficiente porque los elementos de $A$
están en un conjunto.
Usando la estructura \texttt{set},
la complejidad temporal del algoritmo es $O(n \log n)$.

\subsubsection{Algoritmo 2}

No es necesario mantener un conjunto ordenado,
así que en lugar de la estructura \texttt{set}
también podemos usar la estructura \texttt{unordered\_set}.
Esta es una forma fácil de hacer el algoritmo
más eficiente, porque solo tenemos que cambiar
la estructura de datos subyacente.
La complejidad temporal del nuevo algoritmo es $O(n)$.

\subsubsection{Algoritmo 3}

En lugar de estructuras de datos, podemos usar la ordenación.
Primero, ordenamos ambas listas $A$ y $B$.
Después de esto, iteramos a través de ambas listas
al mismo tiempo y encontramos los elementos comunes.
La complejidad temporal de la ordenación es $O(n \log n)$,
y el resto del algoritmo funciona en tiempo $O(n)$,
por lo que la complejidad temporal total es $O(n \log n)$.

\subsubsection{Comparación de eficiencia}

La siguiente tabla muestra qué tan eficientes
son los algoritmos anteriores cuando $n$ varía y
los elementos de las listas son enteros aleatorios
entre $1 \ldots 10^9$:

\begin{center}
\begin{tabular}{rrrr}
$n$ & Algoritmo 1 & Algoritmo 2 & Algoritmo 3 \\
\hline
$10^6$ & $1.5$ s & $0.3$ s & $0.2$ s \\
$2 \cdot 10^6$ & $3.7$ s & $0.8$ s & $0.3$ s \\
$3 \cdot 10^6$ & $5.7$ s & $1.3$ s & $0.5$ s \\
$4 \cdot 10^6$ & $7.7$ s & $1.7$ s & $0.7$ s \\
$5 \cdot 10^6$ & $10.0$ s & $2.3$ s & $0.9$ s \\
\end{tabular}
\end{center}

Los algoritmos 1 y 2 son iguales excepto que
usan diferentes estructuras de conjuntos.
En este problema, esta elección tiene un efecto importante en
el tiempo de ejecución, porque el Algoritmo 2
es 4–5 veces más rápido que el Algoritmo 1.

Sin embargo, el algoritmo más eficiente es el Algoritmo 3
que utiliza la ordenación.
Solo usa la mitad del tiempo en comparación con el Algoritmo 2.
Curiosamente, la complejidad temporal de ambos
Algoritmo 1 y Algoritmo 3 es $O(n \log n)$,
pero a pesar de esto, el Algoritmo 3 es diez veces más rápido.
Esto se puede explicar por el hecho de que
la ordenación es un procedimiento simple y se realiza
solo una vez al principio del Algoritmo 3,
y el resto del algoritmo funciona en tiempo lineal.
Por otro lado,
el Algoritmo 1 mantiene un complejo árbol binario balanceado
durante todo el algoritmo.