Algoritmos I - análisis asintótico

Mar 6, 2025

# Introducción

Esta es la primera parte de una serie de posts en los que hablaré sobre algoritmos y cómo analizarlos. Para poder analizar algoritmos necesitamos desbloquear un par de cosas:

Análisis asintótico y orden de complejidad, que es lo que vamos a ver en este post.
Análisis del tiempo de ejecución de un algoritmo, a través del cuál se analiza un algoritmo estructuralmente para, posteriormente, poder hacer el análisis asintótico del mismo. Este apartado lo cubriré en profundidad en un futuro post pero dejaré un ejemplo al final.

# Por qué medir la eficiencia de un algoritmo

Venga, te presento los siguientes algoritmos de ordenación, ¿cuál dirías que es más eficiente?

quizás sabes la respuesta pero, ¿sabrías justificar por qué?

Insertion sort

void insertionsort(int[] arr) {
    for (int j = 1; j < arr.length; j++) {
        int i = j - 1;
        while (i >= 0 && arr[i] > arr[i+1]) { 
            swap(arr, i, i+1);
            i--;
        }
    }
}

Merge sort

void mergesort(int[] arr, int from, int to) {
    if (arr.length == 1) return;
    
    int mid = (from + to) / 2;
    mergesort(arr, from, mid);
    mergesort(arr, mid + 1, to);

    merge(arr, from, mid, to);
}

Así a simple vista tampoco parece que haya mucha diferencia. El número de líneas de código es similar, no parece que en ninguno haya cálculos muy complejos… Entonces, ¿cómo lo hacemos? Quizá se te pase por la cabeza decir: “bueno pues voy haciendo pruebas manualmente con conjuntos de datos de diferente tamaño, más pequeños y más grandes, y a ver cuál termina primero”. Aunque poco práctico, podría ser una primera aproximación, pero tiene un problema considerable; estarías probado cómo se comporta el algoritmo en tu hardware. Lo cual no es extrapolable a cómo se comportaría el mismo algoritmo en una máquina distinta.

Para solucionar esto se estableció un marco teórico, matemático, a través del cual puedes abstraerte del hardware y medir de forma analítica el rendimiento de tu algoritmo. Este marco matemático se llama análisis asintótico y básicamente se encarga de categorizar el tiempo de ejecución de un algoritmo dado cuando el conjunto de datos con el que trabaja crece sin límite.

Cuando decimos asintótico nos referimos al comportamiento de una función cuando los datos de entrada tienden a infinito.

# La “big picture”

Fuente: https://www.bigocheatsheet.com

A poco que busques información sobre notación asintótica te cruzarás con esta imagen o con una similar. Básicamente representa las categorizaciones que comúnmente usamos para clasificar algoritmos (existen muchas más categorías), donde los algoritmos con mejor rendimiento se encontrarían paralelos (más bien apoyados) al eje $x$ e iría empeorando el rendimiento a medida que nos alejamos.

Para empezar, vamos a desglosar un poco esas categorías en orden decreciente al rendimiento, es decir, los más eficientes primero, categorizándolos usando la notación $\Omicron(x)$ .

$\Omicron(1)$ : Implica que el tiempo de ejecución es constante porque no depende del tamaño de entrada de datos.

Por ejemplo, declarar una variable tiene un tiempo de ejecución constante. De esta forma nos abstraemos del hardware, ya que declarar una variable en un ordenador de los 90 o en un servidor de alta capacidad muy moderno tiene el mismo coste (asintóticamente hablando).

$\Omicron(log(n))$ : Rendimiento logarítmico, prácticamente se puede considerar constante porque crece muy lentamente a medida que el número de datos de entrada aumenta.

Por ejemplo, supongamos que diseñamos un algoritmo que es capaz de ordenar un conjunto de elementos en tiempo logarítmico. Si el conjunto de datos tiene, por ejemplo, 10 elementos, mi algoritmo tardaría 1 milisegundo en resolver el problema. Para 100 elementos, tardaría 2 milisegundo, para 1000 tardaría 3 milisegundo, y así sucesivamente. Encontrar un elemento dado en una lista de elementos previamente ordenada tiene complejidad logarítmica.

Actualmente no existe ningún algoritmo de ordenación capaz de ordenar con esta complejidad asintótica.

$\Omicron(n)$ : Tiempo lineal, lo cual implica que el rendimiento del algoritmo es proporcional al tamaño de datos de entrada. Por ejemplo, recorrer todos los elementos de una lista para mostrarlos en pantalla tiene complejidad lineal.
$\Omicron(n\cdot log(n))$ : Tiempo cuasilineal, un poco peor que lineal pero aún dentro de un rango aceptable. Algoritmos con estos tiempos de ejecución aún son aceptables cuando el tamaño de entrada es muy muy grande.

Todos los algoritmos de ordenación basados en comparaciones binarias $^*$ (la mayoría, vamos) tienen una complejidad asíntótica de $\Omega(n \cdot log(n))$ .

$^*$ Comparaciones binarias se refiere a cualquier comparación lógica en la que intervengan dos elementos: $>, <, \leq, \ge, = ...$

$\Omicron(n^2)$ : tiempo cuadrático o por fuerza bruta, es el tope máximo (siendo muy generoso) que podríamos tildar de “aceptable” (que no eficiente) en un algoritmo. Hay algunos algoritmos que corren en este orden de crecimiento y no tenemos nada mejor, véase por ejemplo el método Streasen para multiplicar matrices.
$\Omicron(2^n)$ , $\Omicron(n!)$ : Estos dos los voy a tratar bajo un mismo punto porque el rendimiento de un algoritmo que caiga en cualquiera de estos tiempos asíntóticos no es manejable para ningún ordenador cuando el número de elementos de entrada aumenta. El famoso problema del viajante recae en este orden de crecimiento.

# Notación $\Omicron$

Primero veámos la idea intuitiva de qué se quiere representar con esta notación y después vemos la definición formal.

La notación $\Omicron(n)$ (conocida como big-O y usada como O grande de $n$ o O de $n$ ) representa una cota superior asintótica para una función a partir de un valor dado. Es decir, para valores suficientemente grandes de $n$ , la función $f(n)$ crece como mucho igual que $g(n)$ dentro de un factor constante. Este hecho se representa como $f(n) = \Omicron(g(n))$ .

Cuando decimos que un algoritmo es del orden de crecimiento de $\Omicron(g(n))$ , indicamos que la función $f(n)$ crecerá como mucho igual que $g(n)$ , de ahí lo de “cota superior”. Puede ser mejor dadas ciertas circunstancias, pero con esta notación indicamos el tope por arriba. Os dejo un pequeño esbozo de cómo se representaría una función $f(n)$ dentro de $\Omicron(g(n))$ :

Normalmente, cuando hacemos este tipo de análisis, la complejidad asíntótica se da para el peor de los casos, es decir, el rendimiento que tendría nuestro algoritmo si todas las condiciones que lo harían más eficiente no son favorables.

De forma intuitiva se ve a que no aporta mucha información decir cómo de eficiente es un algoritmo cuando las condiciones le son totalmente favorables. Por ejemplo, decir que nuestro algoritmo tiene complejidad constante $\Omicron(1)$ a la hora de ordenar datos porque dichos datos ya está previamente ordenados no aporta ningún valor puesto que no podemos sacar información a partir de eso.

Una vez vista la idea general, pasemos a la definición formal y la repasamos:

\Omicron(g(n)) = \set{f(n) : \exists c > 0, \exists k \geq 0 ( f(n) \leq c \cdot g(n) ) \space \forall n \geq k}

La expresión anterior dice que $\Omicron(g(n))$ es el conjunto de funciones $f(n)$ para las cuales existen contantes $c$ y $k$ tal que $f(n)$ es menor o igual a una constante $c$ multiplicada por ese $g(n)$ para todo $n$ mayor que un $k$ dado. Normalmente “abusamos” de la notación y, cuando decimos que $f(n) = \Omicron(g(n))$ , en realidad estamos diciendo que nuestro $f(n)$ pertecene a esa familia de funciones $g(n)$ porque existen constanten $c$ y un $k$ que satisfacen dicha desigualdad.

Decir que $f(n) = \Omicron(g(n))$ es un uso poco ortodoxo matemáticamente hablando, ya que si $\Omicron(g(n))$ representa un conjunto de funciones lo normal sería decir que $f(n) \in \Omicron(g(n))$ . Aún así hacer este uso de la notación tiene sus ventajas, ya que así podemos usar las notaciones asintóticas dentro de ecuaciones “tradicionales”, por ejemplo, diciendo $T(n) = T(\dfrac{n}{2}) + \Omicron(n)$

Pongamos un par de ejemplos prácticos para que se vea claramente: ¿ $x^2 + 2x + 1 = \Omicron(x^2)$ ?

Según la definición, debería haber una constante $c$ y un valor mínimo de $k$ tal que, multiplicar esa $c$ por $x^2$ , (nuestra $g(x)$ ) hace que $x^2 + 2x + 1 \leq c \cdot x^2$ sea cierto para todo $x > k$ . Un poco de álgebra y desarrollamos la desigualdad:

\begin{align*} x^2 + 2x + 1 \leq c \cdot x^2 \\ \leq x^2 + 2x^2 + x^2 \\ = 4x^2 \end{align*}

Pues ahí tenemos lo que buscábamos. Hemos encontrado valores para $c=4$ y $k=1$ en este caso. Dado que esta notación representa un conjunto de funciones hay otros muchos valores para $c$ y $k$ que cumplen la desigualdad, pero lo importante es que hay valores que cumplen para todo $x$ . Simplemente encontrando valores que satisfagan $c$ y $k$ (a veces llamados testigos) es suficiente.

De la misma forma podríamos demostrar lo contrario, que una función no pertenece a un conjunto de funciones. Por ejemplo, ¿ será cierto que $n^2 = \Omicron(n)$ ?

\begin{align*} n^2 \leq c \cdot n \\ = n \cdot n \leq n \\ = n \leq 1 \end{align*}

Dado que $n$ crece sin límite, no se cumple que para todo $n$ esa condición se cumpla, ya que solo se cumple para $n=1$ . Por tanto $n^2 \neq \Omicron(n)$ .

# Notación $\Omega$

Todo lo que he contado para $\Omicron(g(n))$ aplica para esta notación.

La notación $\Omega(n)$ (omega de n o big-Omega) representa a una cota inferior asintótica. Es decir, para valores suficientemente grandes de $n$ , la función $f(n)$ crece, al menos, como $g(n)$ dentro de un factor constante. Este hecho se representa como $f(n) = \Omega(g(n))$ .

Dejo por aquí la definición formal:

\Omega(g(n)) = \set{f(n) : \exists c > 0, \exists k \geq 0 ( f(n) \geq c \cdot g(n) ) \space \forall n \geq k}

Para practicar, vamos a usar el mismo ejemplo de arriba: ¿ será $x^2 + 2x + 1 = \Omega(x^2)$ ?

Como antes, debemos encontrar valores para $c$ y $k$ que cumplan, así que usemos la definición y veamos si algebráicamente podemos adaptar el resultado:

\begin{align*} x^2 + 2x + 1 \geq c \cdot x^2 \\ \end{align*}

Si tomamos $c=1$ y restamos $x^2$ a ambos miembros:

2x + 1 \geq 0 \medspace \medspace \medspace

Resolvemos para $x$

x \geq -\dfrac{1}{2}

Y ya lo tendríamos. Para $x \geq -\dfrac{1}{2}$ , eligiendo valores $c=1$ y $k \geq 1$ , tendríamos que la desigualdad se cumple para todo $x \geq k$ . Concluimos que $x^2 + 2x + 1 = \Omega(x^2)$ .

# Notación $\Theta$

Por último presentamos la notación $\Theta$ , que es una mezcla de las dos anteriores:

$\Theta(n)$ (theta de n o big-Theta) es una notación que representa una cota ajustada, tanto “por arriba” como “por abajo”. Es decir, si decimos que una función $f(n)$ = $\Theta(n^2)$ implica que la función $f(n)$ se comporta igual que $g(n)$ (asintóticamente hablando) a medida que el número de datos de entrada aumenta.

Si has visto o recuerdas algo de cálculo, quizá las dos funciones anteriores te recuerden a los límites de una función cuando se aproximan por izquierda y por derecha (salvando las distancias). Pues esta notación sería como el teorema del sándwich.

De hecho, una vez entendidas las notaciones anteriores, la definición formal de esta no tiene mucha diferencia:

\Theta(g(n)) = \set{f(n) : \exists c_1,c_2 > 0, \exists k \geq 0 (c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) ) \space \forall n \geq k}

Teniendo en cuenta las definiciones anteriores y esta, se puede derivar el siguiente teorema:

f(n) = \Theta(g(n)) \iff f(n) = \Omicron(g(n)) \land f(n) = \Omega(g(n))

Con esto concluimos el apartado de notaciones asintóticas. Existen dos notaciones más que no voy a cubrir aquí porque no suelen aparecer tanto, aunque las dejaré como referencia: little-o y little-omega.

# Pero y todo esto, ¿cómo se aplica?

Como comentaba en la introducción, el análisis asintótico es solo “una pata” de todas las que sustenta el análisis de algoritmos. Para cerrar el post voy a dejar el análisis de uno de los algoritmos que mencioné arriba, insertion sort, aunque para ello utilizaré técnicas que no están descritas en esta entrada pero que explicaré en un futuro.

# Análisis de insertion sort

void insertionsort(int[] arr) {
    for (int j = 1; j < arr.length; j++) {
        int i = j - 1;
        while (i >= 0 && arr[i] > arr[i+1]) {
            swap(arr, i, i+1);               
            i--;                             
        }                                    
    }
}

Insertion-sort es un algoritmo de ordenación muy fácil de entender. Imaginemos una baraja de cartas, sin ordenar, puesta boca abajo en una mesa. Vamos levantando cartas con la mano derecha y colocándolas en la izquierda, asegurando que siempre que añadamos una carta a la mano izquierda la coloquemos ordenada en la posición que corresponda (orden ascendente, por ejemplo). De esta forma todo lo que hay en el montón boca abajo está desordenado y lo que tenemos en la mano izquierda ordenado.

# Bucle while

void insertionsort(int[] arr) {
    for (int j = 1; j < arr.length; j++) {
        int i = j - 1;
        while (i >= 0 && arr[i] > arr[i+1]) {
            swap(arr, i, i+1);
            i--;
        }
    }
}

Primero analicemos el bucle while. Si hacemos una tabla de iteración tenemos que:

Iteración	i
1	$j-1$
2	$j-2$
3	$j-3$
…	…
k	$j-k$

Donde $k$ es la k-ésima iteración (un número de iteración random, la que sea, no importa). La condición de parada del bucle es $i \geq 0$ , así que resolviendo para $k$ tenemos que

j - k = 0 \implies k = j

Por tanto, cuando la iteración $k$ es la última tenemos que el bucle se ha ejecutado $j$ veces. Asumiendo $\Theta(1)$ para las líneas 4 y 5 tenemos que el coste del bucle while es de $\Theta(j)$ .

# Bucle for

void insertionsort(int[] arr) {
    for (int j = 1; j < arr.length; j++) {
        int i = j - 1;
        while (i >= 0 && arr[i] > arr[i+1]) {
            swap(arr, i, i+1);               
            i--;                             
        }                                    
    }
}

Ahora centrémonos en el bucle for desde las líneas 2 a 5. Ya sabemos que el bucle while tiene una complejidad de $\Theta(j)$ , lo obviamos y nos centramos en el resto de líneas de código que, de hecho, solo hay una. Esta línea es la asignación de una variable, y sabemos que eso tiene tiempo constante, por tanto la línea 3 tiene complejidad $\Theta(1)$ .

Pues ya solo nos queda analizar conjuntamente el bucle for y el while. Para ello usamos una sumatoria desde $j=1$ hasta $n$ (que es el rango del bucle for):

\sum\limits_{j=1}^{n} \Theta(j) = \sum\limits_{j=1}^{n} c \cdot j = c \cdot \sum\limits_{j=1}^{n} j = \dfrac{n(n+1)}{2} = \Theta(n^2)

Lo que nos queda al manipular la sumatoria es una progresión aritmética (la suma de los primeros $n$ términos o suma de Gauss), que tiene forma cerrada conocida: $\dfrac{n(n+1)}{2}$ .

Concluir entonces que el algoritmo insertion sort tiene complejidad cuadrática o $\Theta(n^2)$ y, como hemos visto en esta entrada, es un algoritmo muy poco eficiente.

Cualquier duda, comentario, mejora o error en el footer está mi correo personal. ¡Hasta la próxima!