Concepto De Complejidad De Algoritmos.

Concepto De Complejidad De Algoritmos.

Algoritmo, el conjunto de pasos para resolver un problema, mientras que complejidad significa la cantidad de recursos que se utilizan para llegar a una meta.

Un algoritmo será mas eficiente comparado con otro, siempre que consuma menos recursos, como el tiempo y espacio de memoria necesarios para ejecutarlo.

La complejidad de un algoritmo es aquella función que da el tiempo de y/o el espacio utilizado por el algoritmo en función del tamaño de la entrada.

Cada algoritmo guarda una estrecha relación con una estructura de datos. Por ello, no siempre es posible utilizar el algoritmo más eficiente, puesto que la elección de las estructuras de datos depende de varias cuestiones, incluida la de qué tipo de datos administramos y la frecuencia con que se realizan diferentes operaciones sobre ellos. Así, deberemos encontrar una situación compromiso entre tiempo y compromiso utilizados. En general, si aumentamos el espacio necesario para almacenar los datos, conseguiremos un mejor rendimiento en el tiempo y viceversa.

La eficiencia de un algoritmo puede ser cuantificada con las siguientes medidas de complejidad:

1. Complejidad Temporal o Tiempo de ejecución. Tiempo de cómputo necesario para ejecutar algún programa.

2. Complejidad Espacial. Memoria que utiliza un programa para su ejecución, La eficiencia en memoria de un algoritmo indica la cantidad de espacio requerido para ejecutar el algoritmo; es decir, el espacio en memoria que ocupan todas las variables propias al algoritmo. Para calcular la memoria estática de un algoritmo se suma la memoria que ocupan las variables declaradas en el algoritmo. Para el caso de la memoria dinámica, el cálculo no es tan simple ya que, este depende de cada ejecución del algoritmo.

Este análisis se basa en las Complejidades Temporales, con este fin, para cada problema determinaremos una medida N, que llamaremos tamaño de la entrada o número de datos a procesar por el programa, intentaremos hallar respuestas en función de dicha N.

El concepto exacto que cuantifica N dependerá de la naturaleza del problema, si hablamos de un array se puede ver a N como el rango del array, para una matriz, el número de elementos que la componen; para un grafo, podría ser el número de nodos o arcos que lo arman, no se puede establecer una regla para N, pues cada problema acarrea su propia lógica y complejidad.

Tiempo De Ejecución De Un Algoritmo.

Período transcurrido entre el inicio y la finalización del algoritmo:

- Tiempo de ejecución constante. Significa que la mayoría de las instrucciones se ejecutan una vez o muy pocas.

- logN. Tiempo de ejecución logarítmico. Se puede considerar como una gran constante. La base del logaritmo (en informática la más común es la base 2) cambia la constante, pero no demasiado. El programa es más lento cuanto más crezca N, pero es inapreciable, pues logN no se duplica hasta que N llegue a N2.

- N. Tiempo de ejecución lineal. Un caso en el que N valga 40, tardará el doble que otro en que N valga 20. Un ejemplo sería un algoritmo que lee N números enteros y devuelve la media aritmética.

- N•logN. El tiempo de ejecución es N•logN. Es común encontrarlo en algoritmos como Quick Sort y otros del estilo divide y vencerás. Si N se duplica, el tiempo de ejecución es ligeramente mayor del doble.

- N2. Tiempo de ejecución cuadrático. Suele ser habitual cuando se tratan pares de elementos de datos, como por ejemplo un bucle anidado doble. Si N se duplica, el tiempo de ejecución aumenta cuatro veces. El peor caso de entrada del algoritmo Quick Sort se ejecuta en este tiempo.

- N3. Tiempo de ejecución cúbico. Como ejemplo se puede dar el de un bucle anidado triple. Si N se duplica, el tiempo de ejecución se multiplica por ocho.

- 2N. Tiempo de ejecución exponencial. No suelen ser muy útiles en la práctica por el elevadísimo tiempo de ejecución. El problema de la mochila resuelto por un algoritmo de fuerza bruta -simple vuelta atrás- es un ejemplo. Si N se duplica, el tiempo de ejecución se eleva al cuadrado.

EJEMPLO COMPLEJIDAD DE TIEMPO DE EJECUCIÓN DE UN ALGORITMO

El tiempo de ejecución se mide contando el número de pasos de programa.

1. Los comentarios y las instrucciones de declaración no son pasos de programa.

2.

...