Programación de Algoritmos: Time Complexity – Space Complexity

De manera simple:

Time Complexity, o Complejidad del Tiempo es cuantas operaciones haces con los datos de entrada (el input).

Space Complexity, o Complejidad del Espacio es cuanta memoria te gastas en variables, incluyendo los datos de entrada (el input).

Un algoritmo es un proceso, independiente de lenguaje, una serie de pasos.

Una programación de un algoritmo es una implementación del mismo, en un lenguaje determinado.

Complejidad de Tiempo

Para comprender de que va la complejidad del tiempo, necesitaremos al Matemático, aquel que tiene el don de pensar abstractamente. Existen los siguientes tipos de complejida de tiempo:

• Constante O(1)
• Lineal O(n)
• Cuadrática O(n2)
• Logaritmica O(log n)
• Factorial O(n!)
• Exponencial O(2n)

Se representan con “Big O” o “Omnicron”, que es la O Mayúscula y una notación matemática. Para expresar a lo que se refieren y a entenderlo bien, vamos a usar un arreglo como entrada.

Complejidad de Tiempo Constante, O(1).-

Esto quiere decir que no tienes que recorrer el arreglo, que con una simple función matemática, como sumas, restas, multiplicaciones, divisiones, exponenciaciones, puedes resolver el problema.

n * (n+1) // 2

Complejidad de Tiempo Lineal, O(n).-

Esto quiere decir que con recorrer el arreglo puedes resolver el problema y obtener la solución:

for(i=0; i<n; i++) {

  // Operaciones aqui

} // end for

Entonces, O(n) Significa que tendrás que hacer “n” operaciones para resolver el problema, y tardarás más entre más grande sea el arreglo, y este tiempo aumentará linealmente.

Complejidad de Tiempo Cuadrática, O(n2).-

Significa que para resolver el problema tienes que recorrer el arreglo para cada elemento del arreglo:

for(i=0; i<n; i++) {

  for(j=0; j<n; j++) {

    // Operaciones aqui

  } // end for j

} // end for i

Entonces, las operaciones que tienes que hacer se multiplican al cuadrado, y crecen cuadráticamente en relación al número de elementos del arreglo de entrada.

Complejidad de Tiempo Logaritmica, O(log n).-

Un logaritmo reduce exponencialmente el número de operaciones necesarias para obtener el resultado.

while( n > 1 ) {

  // Operaciones aqui

  n = n / 2;

} // end while

Aqui estamos reduciendo n a la mitad en cada iteración, por ejemplo en búsqueda binaria, por lo que el número de operaciones necesarias es logaritmica con respecto a la cantidad de elementos en el arreglo, es decir, en lugar de tener que recorrer todo el arreglo, lo haremos un número menor de veces.

Respecto a las complejidades exponenciales y factoriales, estas se usan mucho menos, debido a que disparán el número de operaciones y podríamos utilizarlas solamente en arreglos de números pequeños.

Complejidad de Espacio

La complejidad de espacio es el cálculo de variables que necesitamos para resolver el problema, tiene la misma notación.

Complejidad de Espacio Constante, O(1).-

Significa que necesitamos declarar variables “simples” para resolver el problema, no arreglos.

Complejidad de Espacio Lineal, O(n).-

Significa que necesitamos declarar un arreglo para resolver el problema.

Complejidad de Espacio Cuadrática, O(n2).-

Significa que necesitaremos declarar un arreglo y para cada elemento de ese arreglo, declarar otro arreglo, es decir, un arreglo de arreglos.

Así que cuando tengas un problema que resolver mediante un algoritmo y te den este tipo de notaciones, ya sabes que significan, cuando es la mayor cantidad de variables que puedes declarar y con cuantas iteraciones es posible resolver el problema.

Un saludo a todos, chicos.

L.