¿Cómo Determinar y Medir la Complejidad?

En el vasto universo de la resolución de problemas, ya sea en el desarrollo de software, la investigación científica o la ingeniería de sistemas, una pregunta fundamental emerge: ¿cómo evaluamos la bondad de una solución? No basta con que una solución funcione; es crucial que lo haga de manera eficiente y escalable. Aquí es donde entra en juego el concepto de complejidad, una métrica vital que nos permite entender el rendimiento y los recursos que demanda un método o sistema a medida que crece la magnitud de los desafíos que enfrenta.

Mientras que existen múltiples caminos para llegar a un mismo resultado, no todos son igualmente óptimos. La capacidad de discernir entre una solución brillante y una ineficiente es lo que distingue un buen diseño. Este artículo explorará las diversas facetas de la complejidad, desde su medición en el ámbito algorítmico, donde la Notación Big O es la protagonista, hasta su conceptualización en otras disciplinas y la evaluación de sistemas complejos.

¿Por Qué es Crucial Medir la Complejidad de los Algoritmos?

Un algoritmo es una serie de instrucciones bien definidas para resolver un problema específico. Dado que existen diversas formas de abordar un mismo problema, es imperativo contar con un método para evaluar estas soluciones en términos de rendimiento y eficiencia. Esto se traduce en el tiempo que un algoritmo tardará en ejecutarse y la cantidad total de memoria que consumirá. Para los programadores, esta evaluación es crítica, asegurando que sus aplicaciones funcionen correctamente y ayudándoles a escribir código limpio y optimizado.

Aquí es donde la Notación Big O se convierte en una herramienta indispensable. Es una métrica estándar para determinar la eficiencia de un algoritmo, permitiendo estimar cuánto tiempo se ejecutará el código con diferentes conjuntos de entradas y medir cuán efectivamente escala a medida que aumenta el tamaño de la entrada. Comprenderla es el primer paso para dominar la optimización.

Entendiendo la Notación Big O: La Clave de la Eficiencia Algorítmica

La Notación Big O, también conocida como notación O grande, representa la complejidad del peor caso de un algoritmo. Utiliza términos algebraicos para describir esta complejidad, definiendo el tiempo de ejecución requerido para un algoritmo al identificar cómo cambiará su rendimiento a medida que el tamaño de la entrada crece. Sin embargo, es importante destacar que no indica la velocidad absoluta de ejecución de tu algoritmo, sino su comportamiento relativo.

La Notación Big O mide la eficiencia y el rendimiento de un algoritmo utilizando la Complejidad Temporal y la Complejidad Espacial.

¿Qué son la Complejidad Temporal y Espacial?

Un factor importante que afecta el rendimiento y la eficiencia de un programa es el hardware, el sistema operativo y la CPU que se utilizan. Sin embargo, al analizar el rendimiento de un algoritmo, estos factores no se consideran. En su lugar, lo que importa es la complejidad temporal y espacial como función del tamaño de la entrada.

• La complejidad temporal de un algoritmo especifica cuánto tiempo tardará en ejecutarse como función del tamaño de su entrada.
• De manera similar, la complejidad espacial de un algoritmo especifica la cantidad total de espacio o memoria requerida para ejecutar un algoritmo como función del tamaño de la entrada.

En esta guía, nos centraremos principalmente en la complejidad temporal, proporcionando una hoja de trucos detallada para ayudarte a comprender cómo calcularla para cualquier algoritmo.

¿Por qué la complejidad temporal es una función del tamaño de la entrada?

Para comprender perfectamente el concepto de «como función del tamaño de la entrada», imagina que tienes un algoritmo que calcula la suma de números basándose en tu entrada. Si tu entrada es 4, sumará 1+2+3+4 para obtener 10; si tu entrada es 5, obtendrá 15 (es decir, 1+2+3+4+5).

const calcularSuma = (entrada) => {
 let suma = 0;
 for (let i = 0; i <= entrada; i++) {
 suma += i;
 }
 return suma;
};

En el código anterior, tenemos tres sentencias:

1. Inicialización de suma (let suma = 0;)
2. El bucle for (for (let i = 0; i <= entrada; i++) { suma += i; })
3. La sentencia de retorno (return suma;)

Aunque solo hay tres sentencias principales, debido al bucle, la segunda sentencia se ejecutará según el tamaño de la entrada. Por ejemplo, si la entrada es 4, la segunda sentencia (sentencia 2) se ejecutará 4 veces, lo que significa que todo el algoritmo se ejecutará seis (4 + 2) veces.

En términos sencillos, el algoritmo se ejecutará entrada + 2 veces, donde entrada puede ser cualquier número. Esto demuestra que se expresa en términos de la entrada. En otras palabras, es una función del tamaño de la entrada.

Tipos Fundamentales de Complejidad Temporal (Big O)

En la Notación Big O, existen seis tipos principales de complejidades (tanto temporales como espaciales), que describen cómo el tiempo de ejecución o el espacio de memoria de un algoritmo crecen en relación con el tamaño de la entrada:

• Constante: O(1)
• Lineal: O(n)
• Logarítmica: O(log n)
• Logarítmica Lineal: O(n log n)
• Cuadrática: O(n^2)
• Exponencial: O(2^n)
• Factorial: O(n!)

Antes de ver ejemplos para cada complejidad temporal, comprendamos la tabla de complejidad Big O.

Gráfico de Complejidad Big O

El gráfico de Big O es una notación asintótica utilizada para expresar la complejidad o el rendimiento de un algoritmo como función del tamaño de la entrada. Esto ayuda a los programadores a identificar y comprender completamente el escenario del peor caso y el tiempo de ejecución o la memoria requerida por un algoritmo. La siguiente tabla ilustra la complejidad Big O:

Ahora que comprendes las diversas complejidades temporales, puedes reconocer las mejores, buenas y regulares, así como las malas y peores (siempre evita las complejidades temporales malas y peores).

La siguiente pregunta que surge es cómo saber qué algoritmo tiene qué complejidad temporal. Aquí tienes algunas pautas:

• Cuando tu cálculo no depende del tamaño de la entrada, es una complejidad temporal constante (O(1)).
• Cuando el tamaño de la entrada se reduce a la mitad, quizás al iterar, manejar recursión o lo que sea, es una complejidad temporal logarítmica (O(log n)).
• Cuando tienes un solo bucle dentro de tu algoritmo, es una complejidad temporal lineal (O(n)).
• Cuando tienes bucles anidados dentro de tu algoritmo, es decir, un bucle dentro de otro bucle, es una complejidad temporal cuadrática (O(n^2)).
• Cuando la tasa de crecimiento se duplica con cada adición a la entrada, es una complejidad temporal exponencial (O(2^n)).

Comencemos describiendo la complejidad de cada tiempo con ejemplos. Es importante tener en cuenta que usaré JavaScript en los ejemplos de esta guía, pero el lenguaje de programación no es importante siempre que comprendas el concepto y cada complejidad temporal.

Profundizando en Cada Tipo de Complejidad con Ejemplos

Complejidad Constante: O(1)

Cuando tu algoritmo no depende del tamaño de la entrada n, se dice que tiene una complejidad temporal constante de orden O(1). Esto significa que el tiempo de ejecución siempre será el mismo, independientemente del tamaño de la entrada.

Por ejemplo, si un algoritmo debe devolver el primer elemento de un arreglo. Incluso si el arreglo tiene un millón de elementos, la complejidad temporal será constante si usas este enfoque:

const primerElemento = (arreglo) => {
 return arreglo[0];
};
let puntuaciones = [12, 55, 67, 94, 22];
console.log(primerElemento(puntuaciones));

La función anterior requerirá solo un paso de ejecución, lo que significa que la función tiene un tiempo constante con una complejidad temporal O(1).

Pero como dije antes, hay varias formas de lograr una solución en programación. Otro programador podría decidir primero recorrer el arreglo antes de devolver el primer elemento:

const primerElementoIneficiente = (arreglo) => {
 for (let i = 0; i < arreglo.length; i++) {
 return arreglo[0];
 }
};
let puntuaciones = [12, 55, 67, 94, 22];
console.log(primerElementoIneficiente(puntuaciones));

Este es solo un ejemplo, probablemente nadie haría esto. Pero si hay un bucle, esto ya no es tiempo constante, sino tiempo lineal con la complejidad temporal O(n).

Complejidad Lineal: O(n)

Obtienes complejidad temporal lineal cuando el tiempo de ejecución de un algoritmo aumenta linealmente con el tamaño de la entrada. Esto significa que cuando una función tiene una iteración que recorre un tamaño de entrada de n, se dice que tiene una complejidad temporal de orden O(n).

Por ejemplo, si un algoritmo debe devolver el factorial de cualquier número de entrada. Esto significa que si ingresas 5, debes recorrer y multiplicar 1 por 2 por 3 por 4 y por 5 y luego obtener 120:

const calcularFactorial = (n) => {
 let factorial = 1;
 for (let i = 2; i <= n; i++) {
 factorial = factorial * i;
 }
 return factorial;
};
console.log(calcularFactorial(5));

El hecho de que el tiempo de ejecución dependa del tamaño de la entrada significa que la complejidad temporal es lineal con el orden O(n).

Complejidad Logarítmica: O(log n)

Esto es similar a la complejidad temporal lineal, excepto que el tiempo de ejecución no depende del tamaño de la entrada, sino de la mitad del tamaño de la entrada. Cuando el tamaño de la entrada disminuye en cada iteración o paso, se dice que un algoritmo tiene complejidad temporal logarítmica.

Este método es el segundo mejor porque tu programa se ejecuta para la mitad del tamaño de la entrada en lugar del tamaño completo, ya que el tamaño de la entrada disminuye con cada iteración.

Un gran ejemplo son las funciones de búsqueda binaria, que dividen tu arreglo ordenado basándose en el valor objetivo.

Por ejemplo, supongamos que utilizas un algoritmo de búsqueda binaria para encontrar el índice de un elemento dado en un arreglo:

const busquedaBinaria = (arreglo, objetivo) => {
 let primerIndice = 0;
 let ultimoIndice = arreglo.length - 1;
 while (primerIndice <= ultimoIndice) {
 let indiceMedio = Math.floor((primerIndice + ultimoIndice) / 2);
 if (arreglo[indiceMedio] === objetivo) {
 return indiceMedio;
 }
 if (arreglo[indiceMedio] > objetivo) {
 ultimoIndice = indiceMedio - 1;
 } else {
 primerIndice = indiceMedio + 1;
 }
 }
 return -1;
};
let puntuaciones = [12, 22, 45, 67, 96];
console.log(busquedaBinaria(puntuaciones, 96));

En el código anterior, dado que es una búsqueda binaria, primero obtienes el índice medio de tu arreglo, lo comparas con el valor objetivo y devuelves el índice medio si es igual. De lo contrario, debes verificar si el valor objetivo es mayor o menor que el valor medio para ajustar el primer y último índice, reduciendo el tamaño de la entrada a la mitad.

Debido a que por cada iteración el tamaño de la entrada se reduce a la mitad, la complejidad temporal es logarítmica con el orden O(log n).

Complejidad Cuadrática: O(n^2)

Cuando realizas una iteración anidada, es decir, un bucle dentro de otro bucle, la complejidad temporal es cuadrática, lo cual es horrible.

Una forma perfecta de explicar esto sería si tienes un arreglo con n elementos. El bucle exterior se ejecutará n veces, y el bucle interior se ejecutará n veces por cada iteración del bucle exterior, lo que dará un total de n^2 impresiones. Si el arreglo tiene diez elementos, se imprimirá 100 veces (10^2).

Aquí hay un ejemplo donde se comparan cada elemento de un arreglo para mostrar el índice cuando dos elementos son similares:

const encontrarElementosSimilares = (arreglo) => {
 for (let i = 0; i < arreglo.length; i++) {
 for (let j = 0; j < arreglo.length; j++) {
 if (i !== j && arreglo[i] === arreglo[j]) {
 return `Coincidencia encontrada en ${i} y ${j}`;
 }
 }
 }
 return "No se encontraron coincidencias 😞";
};
const frutas = ["🍓", "🍐", "🍊", "🍌", "🍍", "🍑", "🍎", "🍈", "🍊", "🍇"];
console.log(encontrarElementosSimilares(frutas));

En el ejemplo anterior, hay un bucle anidado, lo que significa que la complejidad temporal es cuadrática con el orden O(n^2).

Complejidad Exponencial: O(2^n)

Obtienes complejidad temporal exponencial cuando la tasa de crecimiento se duplica con cada adición a la entrada (n), a menudo iterando a través de todos los subconjuntos de los elementos de entrada. Cada vez que una unidad de entrada aumenta en 1, el número de operaciones ejecutadas se duplica.

La secuencia recursiva de Fibonacci es un buen ejemplo. Supongamos que se te da un número y quieres encontrar el enésimo elemento de la secuencia de Fibonacci.

La secuencia de Fibonacci es una secuencia matemática en la que cada número es la suma de los dos números precedentes, donde 0 y 1 son los dos primeros números. El tercer número de la secuencia es 1, el cuarto es 2, el quinto es 3, y así sucesivamente... (0, 1, 1, 2, 3, 5, 8, 13, …).

Esto significa que si introduces 6, el sexto elemento de la secuencia de Fibonacci sería 8:

const fibonacciRecursivo = (n) => {
 if (n < 2) {
 return n;
 }
 return fibonacciRecursivo(n - 1) + fibonacciRecursivo(n - 2);
};
console.log(fibonacciRecursivo(6));

En el código anterior, el algoritmo especifica una tasa de crecimiento que se duplica cada vez que se añade un elemento al conjunto de datos de entrada. Esto significa que la complejidad temporal es exponencial con un orden O(2^n).

Complejidad Factorial: O(n!)

Esta es la complejidad temporal más alta y la peor posible. Significa que el tiempo de ejecución crece de forma extremadamente rápida a medida que aumenta el tamaño de la entrada. Un algoritmo con complejidad O(n!) a menudo implica la generación de todas las posibles permutaciones de un conjunto de elementos, lo que lo hace impráctico para cualquier entrada que no sea trivialmente pequeña.

Más Allá de los Algoritmos: La Complejidad en Otros Dominios

La complejidad no es un concepto exclusivo de la informática. En diversas áreas como la física, la biología, las ciencias sociales o la medicina, la complejidad se conceptualiza de manera diferente, aunque siempre compartiendo la necesidad de relacionarla con la predictibilidad y los fenómenos emergentes.

La complejidad puede medirse por la cantidad de información o por la proporción de orden y desorden. En el caso de la cantidad de información, existen dos subtipos principales:

• Profundidad Lógica: Se basa en las características computacionales de un algoritmo, utilizando la longitud de pasos más corta posible y, por ello, tomando en cuenta cierto grado de eficiencia. En biología y medicina, las estructuras tienden a la máxima eficiencia, traduciéndose en longitudes más cortas para transmitir información, como se observa en la corteza cerebral y la retina.
• Profundidad Termodinámica: Se basa en la dependencia de un sistema respecto a su historia y su ensamblaje para ser como es. En este sentido, un ser humano es más complejo que una hormiga, ya que tuvo un proceso evolutivo más largo para adquirir su conformación.

La clave de la medición de la complejidad en estos campos radica en la información y la entropía, ambas estudiables matemáticamente. Un ejemplo es la ecuación de Boltzmann, que describe el comportamiento de sistemas en desequilibrio. La entropía puede medirse incluso en procesos complejos como el estado de conciencia y el número de conexiones neuronales.

Por otra parte, dos medidas de la complejidad como organización son la complejidad efectiva y la complejidad física. La primera distingue propiedades regulares y aleatorias de un sistema, mientras que la segunda considera las características del medio en el que funciona un organismo, como en la genética y la epigenética. La complejidad también puede medirse estadísticamente, un principio conocido como complejidad correspondiente, aplicado en farmacocinética y farmacodinamia.

La Complejidad de los Sistemas: La Métrica MCS

En el ámbito de la ingeniería de sistemas, especialmente en sistemas de soporte vital, la complejidad también se cuantifica de manera específica para evaluar el diseño y la interconexión de componentes. Una Métrica de Complejidad del Sistema (MCS) se define como la suma del número de nodos (N) en el diagrama de bloques del sistema más el número de interacciones unidireccionales (I) entre los nodos. Es decir:

MCS = N + I

Las MCS se determinan fácilmente mediante la inspección directa de los diagramas de bloques de alto nivel de los sistemas. Esta métrica simple pero efectiva permite a los ingenieros comprender la interdependencia y la posible propagación de fallas dentro de un sistema, facilitando el diseño de arquitecturas más robustas y fáciles de mantener.

Preguntas Frecuentes (FAQ)

¿Por qué es importante la Notación Big O?

La Notación Big O es fundamental porque permite a los desarrolladores predecir cómo se comportará un algoritmo en términos de tiempo de ejecución y uso de memoria a medida que el tamaño de la entrada crece. Esto es crucial para escribir código eficiente y escalable, especialmente en aplicaciones que manejan grandes volúmenes de datos o requieren alta velocidad.

¿Cuál es la mejor complejidad Big O?

La mejor complejidad temporal es O(1), o complejidad constante. Esto significa que el tiempo de ejecución del algoritmo no cambia, sin importar cuán grande sea la entrada. Es el escenario ideal donde el algoritmo realiza una cantidad fija de operaciones.

¿La Notación Big O considera el hardware o el lenguaje de programación?

No, la Notación Big O es una medida asintótica de la eficiencia de un algoritmo, lo que significa que describe cómo el tiempo de ejecución (o espacio) crece en relación con el tamaño de la entrada, independientemente de la velocidad del procesador, la cantidad de RAM o el lenguaje de programación específico. Se centra en el número de operaciones relativas, no en el tiempo real en segundos.

¿Cómo se relaciona la complejidad con la eficiencia?

La complejidad es una medida directa de la eficiencia. Una menor complejidad (por ejemplo, O(1) o O(log n)) indica una mayor eficiencia, ya que el algoritmo requiere menos recursos (tiempo o memoria) a medida que la entrada aumenta. Por el contrario, una alta complejidad (como O(n^2) o O(2^n)) sugiere ineficiencia y un rendimiento deficiente para entradas grandes.

¿Se aplica la complejidad solo a la informática?

Aunque la Notación Big O es predominante en informática, el concepto de complejidad se extiende a muchas otras disciplinas. Como se mencionó en el artículo, la complejidad se estudia en física, biología, medicina y ciencias sociales, donde se utilizan diferentes métricas (profundidad lógica, profundidad termodinámica, MCS, etc.) para comprender sistemas complejos y su comportamiento.

Conclusión

La capacidad de determinar y medir la complejidad es una habilidad invaluable, no solo para los desarrolladores de software, sino para cualquier persona que busque optimizar procesos o comprender sistemas intrincados. Desde la eficiencia de los algoritmos definida por la Notación Big O hasta las intrincadas mediciones en la biología y la medicina, la complejidad es un concepto que subyace a la predictibilidad y la escalabilidad de casi todo lo que nos rodea.

Comprender estos principios nos permite no solo escribir mejores algoritmos y construir sistemas más robustos, sino también apreciar la elegancia y la interconexión en el universo. Aún queda mucho por investigar en el terreno de la medición de la complejidad, pero cada avance nos acerca a una comprensión más profunda de cómo funcionan los sistemas y cómo podemos hacerlos más eficientes y resilientes.

Si quieres conocer otros artículos parecidos a ¿Cómo Determinar y Medir la Complejidad? puedes visitar la categoría Calculadoras.