EL TAMAÑO DE UN PROBLEMA

La idea que subyace tras el concepto de complejidad temporal de un algoritmo es, básicamente, medir cuánto tarda en resolver el problema.

Para resolver cualquier problema, son necesarios unos datos de entrada sobre los que trabaja el algoritmo y que describen una ocurrencia concreta del problema que queremos resolver. El algoritmo, finalmente obtiene una o varias soluciones al problema (si es que el problema tiene soluciones).

Sin embargo, debemos tener en cuenta algunas consideraciones. Por ejemplo, piensa en un típico algoritmo para ordenar los elementos de un vector. Seguro que conoces alguno. El algoritmo consta de una serie de instrucciones que se repiten una y otra vez (bucles), y probablemente, de una serie de selecciones (comparaciones) que hacen que se ejecute uno u otro camino dentro del algoritmo.

Se hace necesaria una pregunta: ¿Tardará lo mismo un algoritmo de ordenación en ordenar un vector con 100 valores que uno con 100000 valores?.... Obviamente no. Pues aquí es donde tenemos que empezar a hablar del tamaño o talla del problema.

Un algoritmo de ordenación debería ser capaz de ordenar un vector con cualquier numero de elementos. Sin embargo, el tamaño del vector incide directamente en el tiempo que tarda el algoritmo en resolverse.

Pues cualquier problema tiene un tamaño, que es un valor o un conjunto de valores que se pueden obtener de los datos de entrada y que si varían, normalmente tienen una repercusión en el tiempo que tardará el algoritmo en finalizar (aunque en algunos casos no).

Por ejemplo, del problema de ordenar un vector, la talla del problema nos la da el número de elementos del vector.

En un algoritmo que halle el término n-ésimo de la sucesión de Fibonacci, la talla nos la dá el propio término número n que queremos hallar.

Cada problema tiene uno o varios valores que determinan su talla.

La complejidad se calcula en función de una talla genérica, y no concreta. Por ejemplo, la complejidad de un algoritmo de ordenación se calcula pensando en un array de longitud n, y no 5, 120 o 100000.