En general, complejidad temporal y complejidad espacial son ​​formas de medir la eficiencia de un algoritmo en función de cómo su uso de recursos escala con la tamaño de su entrada. Repasemos los conceptos básicos y algunos ejemplos comunes.

Complejidad del tiempo

La complejidad del tiempo describe la cantidad de tiempo que tarda un algoritmo en completarse según el tamaño de la entrada (a menudo indicado como n).

1. Tiempo constante – O(1):

   • El tiempo de ejecución del algoritmo no cambia con el tamaño de entrada.
   • Ejemplo: acceder a un elemento en una matriz por índice, como en arr[5].

2. Tiempo logarítmico – O(log n):

   • El tiempo de ejecución del algoritmo crece logarítmicamente a medida que aumenta el tamaño de la entrada, lo que significa que divide el problema a la mitad con cada paso.
   • Ejemplo: búsqueda binaria en una matriz ordenada.

3. Tiempo lineal – O(n):

   • El tiempo de ejecución del algoritmo crece linealmente con el tamaño de entrada.
   • Ejemplo: atravesar una matriz de n elementos una vez.

4. Tiempo lineal – O(n log n):

   • Común en algoritmos de clasificación eficientes donde cada elemento se maneja de forma logarítmica, generalmente debido a una división recursiva y una fusión o procesamiento lineal.
   • Ejemplo: ordenación por combinación, ordenación rápida.

5. Tiempo cuadrático – O(n²):

   • El tiempo de ejecución crece proporcionalmente al cuadrado del tamaño de entrada.
   • Ejemplo: bucles anidados, como comparar cada elemento de una matriz con todos los demás elementos.

6. Tiempo cúbico – O(n³):

   • El tiempo de ejecución crece con el cubo del tamaño de entrada. Es poco común, pero puede ocurrir en algoritmos con tres bucles anidados.
   • Ejemplo: Resolver ciertas operaciones matriciales usando algoritmos de fuerza bruta.

7. Tiempo exponencial – O(2^n):

   • El tiempo de ejecución se duplica con cada elemento adicional en la entrada, generalmente a partir de algoritmos recursivos que resuelven subproblemas en todas las combinaciones posibles.
   • Ejemplo: La solución ingenua para la secuencia de Fibonacci, donde cada llamada conduce a dos llamadas más.

8. Tiempo factorial – O(n!):

   • El tiempo de ejecución crece factorialmente con el tamaño de entrada. A menudo a partir de algoritmos que implican generar todas las permutaciones o combinaciones posibles.
   • Ejemplo: Resolver el problema del viajante con fuerza bruta.

Complejidad espacial

La complejidad del espacio mide la cantidad de memoria que utiliza un algoritmo en relación con el tamaño de entrada.

1. Espacio constante – O(1):

   • El algoritmo utiliza una cantidad fija de memoria independientemente del tamaño de entrada.
   • Ejemplo: almacenar algunas variables, como números enteros o contadores.

2. Espacio logarítmico – O(log n):

   • El uso de la memoria crece logarítmicamente, lo que a menudo se ve con algoritmos recursivos que reducen el problema a la mitad en cada paso.
   • Ejemplo: búsqueda binaria recursiva (complejidad del espacio debido a la pila de llamadas).

3. Espacio lineal – O(n):

   • El uso de la memoria crece linealmente con el tamaño de la entrada, algo común cuando se crea una matriz o estructura de datos adicional para almacenar la entrada.
   • Ejemplo: Crear una copia de una matriz de tamaño n.

4. Espacio cuadrático – O(n²):

   • El uso de la memoria crece con el cuadrado del tamaño de entrada, como cuando se almacena una matriz 2D de tamaño n x n.
   • Ejemplo: almacenar una matriz de adyacencia para un gráfico con n nodos.

5. Espacio exponencial – O(2^n):

   • El uso de la memoria crece exponencialmente con el tamaño de la entrada, a menudo en soluciones recursivas que almacenan datos para cada subconjunto posible de la entrada.
   • Ejemplo: Memorización en algoritmos recursivos con muchos subproblemas superpuestos.

Ejemplos prácticos

• Tiempo lineal (O(n)) y espacio lineal (O(n)):

  • Una función que itera a través de una matriz y almacena cada elemento en una nueva matriz.

• Tiempo cuadrático (O(n²)) y espacio constante (O(1)):

  • Una función que tiene dos bucles anidados sobre una matriz pero que no requiere almacenamiento adicional más allá de unas pocas variables.

Analizando la complejidad

Al analizar el código en busca de complejidad temporal y espacial:

1. Identificar los bucles: Los bucles anidados generalmente aumentan la complejidad (por ejemplo, un bucle da ( O(n) ); dos bucles anidados dan ( O(n^2) )).
2. Busque recursividad: las llamadas recursivas pueden generar una complejidad temporal y espacial exponencial, según el factor de ramificación y la profundidad de la recursividad.
3. Considere las estructuras de datos: el uso de estructuras de datos adicionales como matrices, listas o mapas hash puede afectar la complejidad del espacio.

Consejos generales

• La complejidad del tiempo se trata de contar operaciones en función del tamaño de entrada.
• La complejidad del espacio consiste en contar la cantidad de memoria adicional necesaria.

Al evaluar estos factores, puedes estimar qué tan eficientemente se desempeña un algoritmo y cuánta memoria consume según el tamaño de entrada.