Skip to main content

La complejidad algorítmica (o complejidad computacional) es una rama de las ciencias de la computación que se enfoca en clasificar los problemas computacionales de acuerdo a la cantidad de instrucciones en función del tamaño de la entrada de datos del algoritmo.

La complejidad algorítmica de un problema es una función dependiente de la cantidad de datos que recibe dicho algoritmo, cuyo resultado es el numero de instrucciones que se deben completar para resolver el problema.

A la idea del tiempo que consume un algoritmo para resolver un problema le llamamos complejidad temporal y a la idea de la memoria que necesita el algoritmo le llamamos complejidad espacial.

En el siguiente ejemplo, n es considerado la cantidad de datos que se recibe y es un número entero.

//pseudocódigo
funcion ejemplo(n)
empieza 
   variables: a
   para j desde 1 hasta n hacer 
      a=a+j 
   fin para 
   devolver a 
termina

Independientemente de la computadora y lenguaje en donde se ejecute este algoritmo, la complejidad algorítmica mide el número de instrucciones para completar la tarea en función de n.

El ciclo para se ejecutará n veces, y dentro de este ciclo solo hay una instrucción, por lo tanto, esta parte tendra n instrucciones. Por ultimo, se ejecuta la instruccion devolver a una sola vez. De manera que podemos concluir que la función que indica la complejidad algorítmica de este pseudocódigo es n+1.