En el mundo de la programación, la complejidad temporal y espacial son dos conceptos que un buen programador usa para calcular el rendimiento de un algoritmo. En este post aprenderás acerca de qué son, sus reglas y cómo realizar un análisis para crear algoritmos eficientes en tus programas y proyectos profesionales.
Complejidad Temporal
La complejidad temporal se enfoca en medir la rapidez de un algoritmo al resolver un problema. Este tipo de complejidad se mide en función del tamaño de entrada del algoritmo (cuántos datos debe procesar el algoritmo).
Para realizar una adecuada medición de la complejidad temporal, es fundamental tener en cuenta diversos factores, tales como:
- Datos de entrada: cuanto mayor sea el tamaño de la entrada, más tiempo demorará el algoritmo en ejecutarse.
- Calidad de código creado por el compilador: un código bien escrito y optimizado puede tener un impacto significativo en la velocidad de ejecución del algoritmo, mejorando notablemente su rendimiento.
- Comportamiento y velocidad de la instrucción para ejecutar el programa: algunos lenguajes de programación son más eficientes que otros en términos de velocidad de ejecución.
- Complejidad de tiempo del algoritmo: algunos algoritmos son más eficientes que otros en términos de complejidad temporal.
Ten en cuenta que los puntos 1 y 4 son el enfoque principal para realizar el análisis y calcular la eficiencia de un algoritmo. Un ejemplo, el tiempo de ejecución de una instrucción se considera constante. En el caso de los algoritmos, es necesario sumar los tiempos de ejecución de cada instrucción para obtener el tiempo total de ejecución del algoritmo. El tiempo total de ejecución del algoritmo se expresa como T(n), donde n es el tamaño de la entrada del algoritmo.
Dentro de este ejemplo, existe una notación ampliamente utilizada para describir la complejidad de un algoritmo: la Big O Notation (Notación O Grande). En este post, utilizaremos esta notación para explicar de manera más precisa la eficiencia del algoritmo.
En caso de no estar familiarizado con la Notación Big O o haberte sentido confundido, no temas, te sugiero revisar este post sobre análisis asintótico, donde explica a mayor profundidad sobre este tema.
Casos de estudio
Los casos de estudio son una parte esencial del análisis asintótico en la programación. Nos ayudan a entender mejor el rendimiento de un algoritmo y cómo podemos optimizarlo para mejorar la eficiencia de una aplicación.
Existen 3 casos de estudio a tomar en cuenta al realizar un análisis asintótico:
- Peor caso: Es el mayor tiempo de ejecución en ejecutar un algoritmo. Es decir, el tiempo de ejecución del algoritmo será el peor cuando se presente la entrada más grande posible.
- Mejor caso: Es el menor tiempo de ejecución en ejecutar un algoritmo. Es decir, el tiempo de ejecución del algoritmo será el mejor cuando se presente la entrada más pequeña posible.
- Caso promedio: Es el tiempo promedio de ejecución para una entrada n. Es decir, es una medida del rendimiento típico del algoritmo.
En la práctica, debes utilizar los casos de estudio para optimizar los algoritmos y mejorar el rendimiento de las aplicaciones. Al examinar los casos de estudio, podrás identificar qué áreas se pueden mejoran y trabajar en ellas para obtener un algoritmo más eficiente en términos de tiempo de ejecución.
Reglas para el cálculo de la complejidad temporal
Existen ciertas reglas para calcular la eficiencia de un algoritmo. En la Big O Notation, las reglas de cálculo son las siguientes:
- Declaraciones de variables y comentarios no se toman en cuenta, ya que no afectan la eficiencia del algoritmo.
- Las operaciones básicas (como suma, resta, multiplicacion, comparación, etc), tienen una eficiencia de O(1).
- Las condiciones (if, else) y los bucles (for, while) tienen una eficiencia de O(1) si no contienen operaciones complejas, como otra iteración o una recursión.
- Una iteración simple (for, while) tiene una eficiencia de O(n), donde n es el tamaño del conjunto de datos que se está procesando.
- Una doble iteración (dos ciclos anidados) tiene una eficiencia de O(n^2).
- Una iteración con n operaciones complejas tiene una eficiencia de O(n * k), donde k es el número de operaciones complejas en cada iteración.
¿Cómo calcular la complejidad temporal?
Calcular la complejidad temporal de un algoritmo según la notación «big O» requiere los siguientes pasos:
En primer lugar, identifica las operaciones básicas: lo inicial es distinguir las operaciones fundamentales que se realizan en el algoritmo. Por ejemplo, si el algoritmo comprende operaciones aritméticas simples, asignaciones de variables, comparaciones, etc.
Luego, calcula la frecuencia de operaciones básicas: una vez identificadas las operaciones fundamentales, debes calcular cuántas veces se realizan en base al tamaño de entrada. Por ejemplo, si el algoritmo tiene un ciclo for que itera n veces y realiza una operación aritmética simple en cada iteración, entonces generará n operaciones aritméticas.
A continuación, determina la complejidad temporal: después de calcular la frecuencia de operaciones básicas, debes decidir la complejidad temporal. Esto se hace eliminando los términos menos significativos y conservando solo el que domina el tiempo de ejecución a medida que el tamaño de entrada aumenta enormemente. Por ejemplo, si la complejidad temporal es n^2 + n + 1, se eliminarán los términos menos importantes (n y 1) dejando solo el dominante (n^2), lo que resulta en una complejidad temporal de O(n^2).
Por último, expresa la complejidad temporal en notación «big O»: debes indicar la complejidad temporal en notación «big O» usando el término que domina el tiempo de ejecución a medida que el tamaño de entrada crece enormemente. Es decir, si la complejidad temporal es O(n^2), esto significa que el tiempo de ejecución del algoritmo aumentará proporcionalmente al cuadrado del tamaño de entrada.
Ilustremos toda esta teoría con 3 ejemplos intuitivos, utilizando Javascript. Toma en cuenta que estos ejemplos se puede aplicar a cualquier otro lenguaje de programación o en psudocódigo.
Ejemplo 1: Suma de los elementos de un array
function sumaArray(array) {
let suma = 0; // Declaración: no se toma en cuenta
for (let i = 0; i < array.length; i++) { // Iteración: O(n)
suma += array[i]; // Operación: O(1)
}
return suma; // Operación: O(1)
}
const array = [1, 2, 3, 4, 5];
console.log(sumaArray(array)); // Salida: 15En este ejemplo, la función sumaArray recibe un array como parámetro y devuelve la suma de todos los elementos del array. La función utiliza una iteración para recorrer todos los elementos del array, lo cual tiene una eficiencia de O(n). Dentro de la iteración for, calcula una operación de suma, lo que genera como resultado una eficiencia de O(1). Finalmente, la función devuelve la suma, lo cual también tiene una eficiencia de O(1).
Por lo tanto, la eficiencia total de la función sumaArray es de O(n), ya que la iteración es la operación que domina el tiempo de ejecución con una complejidad de O(n).
Ejemplo 2: Buscar un elemento en un array
function buscarElemento(array, elemento) {
for (let i = 0; i < array.length; i++) { // Iteración: O(n)
if (array[i] === elemento) { // Condicional: O(1)
return true; // Operación: O(1)
}
}
return false; // Operación: O(1)
}
const array = [1, 2, 3, 4, 5];
console.log(buscarElemento(array, 3)); // Salida: true
En este ejemplo, la función buscarElemento recibe un array y un elemento como parámetros, y devuelve true si el elemento se encuentra en el array y false en caso contrario. La función utiliza una iteración para recorrer todos los elementos del array, lo cual tiene una eficiencia de O(n). Dentro del ciclo, se realiza una operación de comparación (el condicional), lo cual tiene una eficiencia de O(1). Si el elemento se encuentra en el array, la función devuelve true, lo cual también tiene una eficiencia de O(1). Si el elemento no se encuentra en el array, la función devuelve false, lo cual también tiene una eficiencia de O(1).
En otras palabras, la eficiencia total de la función buscarElemento es de O(n), debido a que la iteración es la operación que domina el tiempo de ejecución con una complejidad de O(n).
Ejemplo 3: Ordenar un array
function ordenarArray(array) {
for (let i = 0; i < array.length - 1; i++) { // Iteración: O(n)
for (let j = i + 1; j < array.length; j++) { // Iteración: O(n)
if (array[i] > array[j]) { // Condicional: O(1)
const temp = array[i]; // Operación: O(1)
array[i] = array[j]; // Operación: O(1)
array[j] = temp; // Operación: O(1)
}
}
}
return array; // Operación: O(1)
}
const array = [5, 3, 2, 4, 1];
console.log(ordenarArray(array)); // Salida: [1, 2, 3, 4, 5]
En este último ejemplo, la función ordenarArray recibe un array como parámetro y devuelve el mismo array ordenado de menor a mayor. La función utiliza dos iteraciones anidadas para comparar todos los pares de elementos del array y ordenarlos de menor a mayor. Cada iteración tiene una eficiencia de O(n), lo que da como resultado una eficiencia total de O(n^2) en la complejidad espacial. Dentro del ciclo interior, se realizan tres operaciones de asignación, cada una con una eficiencia de O(1), y un condicional que también tiene una eficiencia de O(1).
Como resultado final, la eficiencia total de la función ordenarArray es de O(n^2), ya que las dos iteraciones anidadas dominan el tiempo de ejecución con una complejidad de O(n^2).
Complejidad Espacial
La complejidad espacial es el estudio del uso de memoria de un algoritmo con respecto al tamaño de los datos de entrada. Sus reglas son similares a la complejidad temporal, es importante conocer la complejidad espacial de un algoritmo para garantizar su eficiencia y escalabilidad.
Reglas para el cálculo de la Complejidad Espacial
Para calcular la complejidad espacial, se utilizan reglas que establecen la cantidad de memoria que se utiliza para almacenar diferentes tipos de datos, entre ellas:
- Tipos primitivos (booleanos, caracteres, enteros, números reales) utilizan una cantidad fija de memoria, que puede variar dependiendo del lenguaje de programación utilizado.
- Los tipos definidos por el usuario (enumeraciones, intervalos) usan una cantidad fija de memoria, la cual suele ser menor que los tipos de datos estructurados.
- Los tipos de datos estructurados (cadenas, arreglos, registros) utilizan una cantidad de memoria proporcional al tamaño de los datos que contienen.
Ahora te mostraré tres ejemplos de cómo se puede aplicar la complejidad espacial en JavaScript para analizar el uso de memoria de un algoritmo:
Ejemplo 1: Crear un arreglo de números aleatorios
function crearArregloAleatorio(tamaño) {
const arreglo = []; // Uso de memoria constante: O(1)
for (let i = 0; i < tamaño; i++) {
arreglo.push(Math.floor(Math.random() * 100)); // Uso de memoria proporcional a 'tamaño': O(n)
}
return arreglo;
}
const arreglo = crearArregloAleatorio(100); // Uso de memoria proporcional a 'tamaño': O(n)
console.log(arreglo);
En este ejemplo, la función crearArregloAleatorio recibe un parámetro tamaño que indica el número de elementos que se van a generar en el arreglo. La función genera un arreglo de números aleatorios y lo devuelve. Para analizar la complejidad espacial de esta función, podemos considerar que la cantidad de memoria utilizada para almacenar el arreglo es proporcional al tamaño del arreglo. En este caso, la eficiencia espacial de la función es O(n), donde n es el tamaño del arreglo.
Ejemplo 2: Multiplicar dos matrices
function multiplicarMatrices(matriz1, matriz2) {
const resultado = []; // Uso de memoria constante: O(1)
const filas1 = matriz1.length;
const columnas1 = matriz1[0].length;
const columnas2 = matriz2[0].length;
for (let i = 0; i < filas1; i++) {
resultado[i] = []; // Uso de memoria proporcional a 'filas1': O(n)
for (let j = 0; j < columnas2; j++) {
let suma = 0; // Uso de memoria constante: O(1)
for (let k = 0; k < columnas1; k++) {
suma += matriz1[i][k] * matriz2[k][j]; // Uso de memoria constante: O(1)
}
resultado[i][j] = suma; // Uso de memoria proporcional a 'filas1' y 'columnas2': O(n^2)
}
}
return resultado;
}
const matriz1 = [
[1, 2],
[3, 4]
];
const matriz2 = [
[5, 6],
[7, 8]
];
const resultado = multiplicarMatrices(matriz1, matriz2); // Uso de memoria proporcional al tamaño de las matrices de entrada: O(n^2)
console.log(resultado);
En este ejemplo, la función multiplicarMatrices recibe dos matrices como parámetros y devuelve su multiplicación. Para analizar la complejidad espacial de esta función, podemos considerar que la cantidad de memoria utilizada para almacenar la matriz resultado es proporcional al tamaño de las matrices de entrada. Creando un resultado de O(n^2) en la complejidad espacial, donde n es el tamaño de las matrices de entrada.
Ejemplo 3: Crear un objeto con propiedades aleatorias
function crearObjetoAleatorio(numPropiedades) {
const objeto = {}; // Uso de memoria constante: O(1)
for (let i = 0; i < numPropiedades; i++) {
const nombrePropiedad = "propiedad_" + i;
objeto[nombrePropiedad] = Math.floor(Math.random() * 100); // Uso de memoria proporcional a 'numPropiedades': O(n)
}
return objeto;
}
const objeto = crearObjetoAleatorio(10); // Uso de memoria proporcional a 'numPropiedades': O(n)
console.log(objeto);
En este ejemplo, la función crearObjetoAleatorio recibe un parámetro numPropiedades que indica el número de propiedades que se van a generar en el objeto. La función genera un objeto con propiedades aleatorias y lo devuelve. Para analizar la complejidad espacial de esta función, podemos considerar que la cantidad de memoria utilizada para almacenar el objeto es proporcional al número de propiedades. El resultado para este ejemplo es O(n) en la complejidad espacial, donde n es el número de propiedades del objeto.
Reto
¿Quieres poner en práctica lo que has aprendido sobre complejidad temporal y espacial en la programación? Te reto a que realices estos tres ejercicios sencillos para calcular el análisis asintótico de diferentes algoritmos.
// Reto 1: Busqueda lineal// Reto 2: Ordenamiento de burbuja// Reto 3: Cálculo del factorialConclusión
Es importante tener en cuenta que la complejidad temporal y espacial no son los únicos factores que deben considerarse al evaluar un algoritmo, sino también la facilidad de implementación, la legibilidad del código y la mantenibilidad del mismo.
En conclusión, comprender la complejidad temporal y espacial es fundamental para diseñar e implementar algoritmos eficientes y optimizar el rendimiento de un programa. Al evaluar la complejidad temporal y espacial de un algoritmo, se puede tomar una decisión informada sobre si vale la pena implementar o no ese algoritmo, considerando los requerimientos del problema en cuestión.