Complejidad de espacio constante y lineal en algoritmos

Como programador, es posible que hayas resuelto muchos desafíos de programación. En la programación, la complejidad del espacio y el tiempo importa mucho cuando necesitamos ejecutar un programa. Nuestro algoritmo debería ser eficiente y debería tomar menos tiempo. Cada vez que escribe una solución para un programa, se requiere algo de memoria para completar, y es importante que nuestro programa tome menos memoria y se ejecute dentro de un período de tiempo determinado. 

Para cualquier programa, la memoria se puede utilizar para lo siguiente…

1. Variables (Esto incluye los valores constantes, valores temporales)
2. Instrucción del programa
3. Ejecución

La complejidad espacial es la cantidad total de memoria que necesita un programa para ejecutar un algoritmo y producir el resultado. Muchas veces los programadores se confunden con el Espacio Auxiliar y la Complejidad del Espacio. Ambos son diferentes. En cualquier algoritmo, el espacio extra o el espacio temporal que utilizamos se conoce como espacio Auxiliar. 

Space Complexity = Auxiliary Space + Input space

En este artículo, comprenderemos el uso de la memoria durante la ejecución y comprenderemos la clasificación de la complejidad del espacio. El algoritmo usa espacio de memoria por tres razones…

1. Espacio de instrucciones: mientras se escribe un algoritmo, la versión compilada de las instrucciones ocupa cierta cantidad de memoria que se conoce como espacio de instrucciones.

2. Pila Ambiental: Se requiere almacenar la información ambiental necesaria para retomar la función suspendida. Esto se usa cuando se llama a un algoritmo dentro de otro algoritmo. En esas situaciones, empujamos las variables actuales a la pila del sistema, donde esperamos una mayor ejecución. Después de eso, lo llamamos dentro del algoritmo.

Tomemos el ejemplo de dos funciones. Función X() y función Y(). Las variables de la función X() se almacenarán temporalmente en la pila del sistema, mientras que la función Y() se llama y ejecuta dentro de la función X().

3. Espacio de datos: durante la ejecución de un programa, cualquier espacio que se requiera para almacenar las constantes y los valores de las variables se considera como espacio de datos.

Nota: Al escribir un algoritmo, solo necesita considerar el espacio de datos. No necesita calcular el espacio de instrucciones y la pila ambiental .

Ahora comprendamos la clasificación de la complejidad del espacio. La complejidad del espacio se puede calcular de dos maneras. Depende del programa. El programa puede ser un programa constante o un programa lineal.

¿Cómo calcular la complejidad del espacio?

En un algoritmo, primero debe calcular la cantidad total de memoria para evaluar la complejidad del espacio. Necesita saber el valor de la memoria utilizada por diferentes tipos de tipos de datos de variables. Para diferentes sistemas operativos o diferentes máquinas. Este valor puede ser diferente para cada máquina, pero el método sigue siendo el mismo.

Tomemos uno de los ejemplos para calcular la complejidad del espacio…

{
   int x = a * b * c;
   return(x);
}

En la expresión anterior, a, b, c y x son tipos enteros. Cada uno de ellos ocupa 4 bytes. Ahora podemos calcular la memoria total. Esto será…

(4(4) + 4) = 20 bytes. 4 bytes adicionales son para el valor de retorno. Aquí necesitamos una cantidad fija de memoria para todas las entradas. Así que este tipo de complejidad se llama Complejidad de Espacio Constante . 

Pasemos a otro ejemplo…

// n is the length of array a[]
int sum(int arr[], int n)
{
int sum = 0;  // 4 bytes for sum
for(int i = 0; i < n; i++) // 4 bytes for i
{  
    sum  = sum + arr[i];  
}
return(sum);
}

• En el ejemplo anterior, necesitamos 4*n bytes de espacio para cada elemento de la array.
• 4 bytes cada uno para sum, n, i y el valor de retorno.

Entonces, la cantidad total de memoria será (4n+12), que aumenta linealmente con un aumento en el valor de entrada n. Esto se llama Complejidad del Espacio Lineal. Si tiene una variable de bucle I, la complejidad del espacio requerido será de 1 palabra. 

Si ha entendido el concepto de calcular la complejidad del espacio del ejemplo anterior, siguiendo un enfoque similar, puede calcular la complejidad cuadrática y de otro tipo, a medida que aumenta la complejidad de un algoritmo. Siempre trate de minimizar la complejidad del espacio de su algoritmo. Menos espacio hace que su algoritmo sea mejor y más eficiente.

Resumen

• O(1) Complejidad: Consideramos complejidad de espacio constante cuando el programa no contiene ningún bucle, función recursiva o llamada a otras funciones. 
• O(n) Complejidad: Consideramos la complejidad del espacio lineal cuando el programa contiene bucles. 

Hoja de trucos de complejidad espacial para algoritmos

• Clasificación de burbujas: O (1)
• Clasificación de selección: O (1)
• Clasificación por inserción: O(1)
• Clasificación por combinación: O(n)
• Clasificación rápida: O(n)
• Clasificación de montón: O (1)
• Radix Sort: O(n+k) donde k — rango de elementos de la array. 

Pensamiento final

La complejidad del espacio juega un papel crucial en la determinación de la eficiencia de un algoritmo. Siempre trate de implementar un algoritmo que tome menos tiempo. Si un programa ocupa mucho espacio en la memoria, el compilador no le permitirá ejecutarlo. Recuerde siempre la siguiente fórmula en complejidad espacial

Space Complexity = Auxiliary space + Space use by input values