Big-O ¿Qué es?

Cuando comenzamos en el mundo de la programación, nos empiezan a decir términos que a veces no terminamos de comprender. En Estructura de Datos podrías haber escuchado del término de "Big-O". Este es un concepto dentro de la complejidad de los algoritmos, los cuales pueden dividirse en dos:

• Complejidad de tiempo
• Complejidad de memoria

Seguramente has visto la siguiente gráfica:

Esta gráfica muestra cómo se comportan las operaciones en cuanto a la complejidad que tienen.

¿Para qué se necesita saber la complejidad?

Cuando creamos un algoritmo, muchas veces puede ser una respuesta correcta a un problema determinado, pero muchas veces existen casos específicos donde estos algoritmos no son eficientes o pueden fallar, o incluso nos limitamos a ciertas cosas que no dependen del programador, como los son el tiempo y memoria que pueden ocupar, por lo que se tiene que pensar en cómo mejorar los algoritmos incluso antes de escribir el código. Es por eso que se busca una complejidad "baja" para estos casos.

La complejidad $O(1)$ es una complejidad constante, la cual es la complejidad más eficiente. Entre más crezca la complejidad, más tiempo tardará en ejecutarse el código.

Tanto la complejidad del tiempo como la de memoria se pueden calcular a grandes razgos. En seguida te doy ejemplos de cómo tener una noción de cómo se calcula.

Complejidad de tiempo

La complejidad de tiempo mide la cantidad de tiempo que un algoritmo tarda en ejecutarse en función del tamaño de la entrada. Describe el comportamiento asintótico del algoritmo a medida que el tamaño de la entrada crece.

1. Identifica las operaciones básicas: Encuentra las operaciones que consumen tiempo de manera significativa (comparaciones, asignaciones).
2. Cuenta el número de operaciones básicas: Estima el número de veces que se ejecutan estas operaciones en términos de $n$ (el tamaño de la entrada).
3. Determina el término dominante: En la expresión resultante, identifica el término que más crece a medida que $n$ aumenta.
4. Expresa en notación Big-O: Elimina constantes y coeficientes no dominantes y expresa el término dominante en notación Big-O.

C++
Copiar
for (int i = 0; i < n; i++) {
    // Operación básica
}

Aquí, la operación básica se ejecuta $n$ veces, por lo que la complejidad de tiempo es $O(n)$.

Complejidad de memoria

La complejidad de memoria mide la cantidad de espacio de memoria que un algoritmo necesita en función del tamaño de la entrada.

1. Identifica las variables y estructuras de datos: Encuentra las variables y estructuras que el algoritmo utiliza.
2. Cuenta la memoria utilizada: Estima la cantidad de memoria utilizada por estas variables y estructuras en términos de $n$.
3. Determina el término dominante: Identifica el término que más crece a medida que nn aumenta.
4. Expresa en notación Big-O: Elimina constantes y coeficientes no dominantes y expresa el término dominante en notación Big-O.

C++
Copiar
int arr[n];
for (int i = 0; i < n; i++) {
    arr[i] = i;
}

Aquí, el arreglo arr ocupa $n$ espacios de memoria, por lo que la complejidad de memoria es $O(n)$.

La diferencia entre estas dos mediciones es que la complejidad de tiempo evalúa cuánto tiempo tarda un algoritmo en ejecutarse, mientras que la complejidad de memoria evalúa cuánta memoria necesita un algoritmo para ejecutarse.

La complejidad de tiempo y memoria son esenciales para evaluar la eficiencia de un algoritmo. Comprender cómo calcularlas te permitirá diseñar algoritmos más eficientes y seleccionar los más apropiados para tus necesidades.

Para finalizar, te dejo este recurso el cual es una página donde encuentras el gráfico mostrado de las complejidades de Big-O, la complejidad de algunas estructuras de datos y la complejidad de algunos algoritmos de ordenamiento.

➡️ Big-O Cheat Sheet ⬅️