Análisis de los algoritmos

Entendemos por algoritmo como un conjunto finito de instrucciones no ambiguas y efectivas que indican cómo resolver un problema, producen al menos una salida, reciben cero o más entradas y, para ejecutarse, necesitan una cantidad finita de recursos. Una instrucción es no ambigua cuando la acción a ejecutar está perfectamente definida.

El tema principal de la investigación es el análisis de los algoritmos: estudia la complejidad espacial y temporal de los algoritmos. 

ANÁLISIS DE LOS ALGORITMOS

El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes.

A la hora de realizar un análisis teórico de algoritmos es común calcular su complejidad en un sentido asintótico, es decir, para un tamaño de entrada suficientemente grande. La cota superior asintótica, y las notaciones omega y theta se usan con esa finalidad. Por ejemplo, la búsqueda binaria decimos que se ejecuta en una cantidad de pasos proporcional a un logaritmo, en O(log(n)), coloquial mente "en tiempo logarítmico". Normalmente las estimaciones asintóticas se utilizan porque diferentes implementaciones del mismo algoritmo no tienen porque tener la misma eficiencia. No obstante la eficiencia de dos implementaciones "razonables" cualesquiera de un algoritmo dado están relacionadas por una constante multiplicativa llamada constante oculta.

Tareas en el Análisis de Algoritmos:

- Determinar qué operaciones se emplean y su costo relativo.

- Determinar conjuntos de datos para exhibir todos los patrones posibles de comportamiento.

- Análisis a priori: se determina una función (de ciertos parámetros) que acote el tiempo de cómputo del algoritmo.

- Análisis a posteriori: estadísticas reales sobre tiempo y memoria.

Tipos de Algoritmos:

* Algoritmos determinísticos: El resultado de cada operación está definido en forma única.

* Algoritmos no-determinísticos. El resultado de cada operación esta determinado por un conjunto de posibilidades.

* Algoritmo polinomial. Es un algoritmo de complejidad polinomial o inferior.

* Algoritmo No-Polinomial. Es un algoritmo de complejidad exponencial o mayor.

COMPLEJIDAD DE ALGORITMOS

Si un conjunto de instrucciones tiene todas las características de un algoritmo, excepto ser finito en tiempo se le denomina proceso computacional. Los sistemas operativos son el mejor ejemplo de proceso computacional, pues están diseñados para ejecutar tareas mientras las haya pendientes, y cuando éstas se terminan, el sistema operativo entra en un estado de espera, hasta que llegan más, pero nunca termina.

La función complejidad, f(n), donde n es el tamaño del problema, da una medida de la cantidad de recursos que un algoritmo necesitará al implantarse y ejecutarse en alguna computadora. Puesto que la cantidad de recursos que consume un algoritmo crece conforme el tamaño del problema se incrementa, la función complejidad es monótona creciente

(f(n) > f(m) ⇔ n > m) con respecto al tamaño del problema. La memoria y el tiempo de procesador son los recursos sobre los cuales se concentra todo el interés en el análisis de un algoritmo, así pues distinguiremos dos clases de función complejidad:

a) Función complejidad espacial. Mide la cantidad de memoria que necesitará un algoritmo para resolver un problema de tamaño n.

b) Función complejidad temporal. Indica la cantidad de tiempo que re- quiere un algoritmo para resolver un problema de tamaño n; viene a ser una medida de la cantidad de CPU que requiere el algoritmo.

COMPLEJIDAD EN EL TIEMPO

◦   El tiempo de Ejecución de un programa se mide en función de N, lo que designaremos como T(N).

◦   Esta función se puede calcular físicamente ejecutando el programa acompañados de un reloj, o calcularse directamente sobre el código, contando las instrucciones a ser ejecutadas y multiplicando por el tiempo requerido por cada instrucción. Así, un sencillo código como:

S1;

for(x = 0; x < N; x++)

S2;

Demanda: T(N) = t1 + t2 * N

Donde t1 es el tiempo que lleva ejecutar la serie S1 de sentencias, y t2 es el que lleva la serie S2.

Habitualmente todos los algoritmos contienen alguna sentencia condicional o selectiva, haciendo que las sentencias ejecutadas dependan de la condición lógica, esto hace que aparezca más de un valor para T(N), es por ello que debemos hablar de un rango de valores.

Cuando se habla del tiempo de ejecución de un algoritmo debe tenerse presente que el tiempo de ejecución exacto de un programa depende de varios factores:

1.- Los datos de entrada

2.- La calidad del condigo generado por el compilador

3.- La maquina donde se ejecuta el programa

4.- La complejidad del tiempo del algoritmo base del programa

En el momento de diseñar y elegir entre posibles alternativas, sin embargo, los tres primero factores generalmente o no se conocían o nos vienen dados. Por lo tanto, el estudio de un algoritmo se centra en su complejidad de tiempo de ejecución. Mejorar su eficiencia generalmente implica reducir su complejidad de tiempo de ejecución.

Cuando se estudia la complejidad de tiempo de ejecución de un algoritmo se define esta en función de los datos de entrada. El estudio sin embargo, depende del tamaño de los datos de entrada, no de los datos concretos. Por ejemplo, supongamos que se requiere estudiar un algoritmo de ordenación que, dada una lista de numero, devuelva la misma lista ordenada ascendentemente. Así, si se quisiera ordenar la lista {2, 1, 3, 1, 5, 8}, se hablaría de una entrada de tamaño de n=6.

Denotemos, pues T(n) la función del tiempo de ejecución de un algoritmo con entrada de tamaño n. T(n) se expresa sin unidades, ya que el tiempo de ejecución exacto depende de muchos otros factores. T(n) representa el numero de operaciones elementales que realiza el algoritmo para obtener la solución. Se consideran operaciones elementales las asignaciones, comparaciones, operaciones aritméticas, etc.

Notación asintótica:

Se a descrito la eficiencia de un algoritmo mediante su función de ejecución, T(n). Debido a que el tiempo de ejecución exacto depende de factores diversos, cuando se escribe que T(n) es una determinada función f(n), por ejemplo f(n)=n² , o f(n)=n* log (n), debe entenderse únicamente que T(n) es proporcional a f(n).

Este concepto de proporcionalidad entre funciones se puede representar formalmente mediante lo que se llama notación asintótica. Esta es la notación que se utiliza cuando se quiere describir la eficiencia de un algoritmo.

Intuitivamente, la notación asintótica sirve para indicar la velocidad de crecimiento de la función del tiempo de ejecución de un algoritmo. Se dice que T(n) es O(f(n)), leído O grande f(n), cuando la velocidad de crecimiento de T(n) esta acotada superiormente por f(n). Así O (f(n)) representa el conjunto de todas las funciones g(n) que crecen, como mucho, tan rápidamente como f(n). Formalmente, este conjunto de funciones se puede definir como se muestra en la siguiente ecuación:

O(f (n)) = O(g (n)) ⇔ f(n) ∈ O(g (n)) ∧ g(n) ∈ O(f (n ))

Técnicas para estimar el tiempo de ejecución:

Para estimar el tiempo de ejecución, se utiliza la técnica de análisis. Esta estimación, se hará en función del numero de operaciones elementales que realiza dicho algoritmo para un tamaño de entrada dado. Entendiendo por operaciones elementales como aquellas operaciones cuyo tiempo de ejecución se puede acortar superiormente por una constante. Así se consideran como operaciones elementales:

-   Operaciones aritméticas básicas (+. -, *, /, %)

-   Asignaciones variables (=)

-   Comparaciones lógicas o relacionales {&&, l l, <>, >=, =<, ==, !=)

-   Acceso a estructuras de datos estáticas y dinámicas

-   Parámetros que llegan a los métodos

-   Instrucciones de salto (break, continúe)

-   Retorno de valores (return)

-   Referencia a objetos

-   Instrucciones condicionales

-   Creación de objetos

-   Expresiones que con incrementos y decrementos

Complejidad Temporal:

Parámetro de medición: Se toma el tamaño de la entrada n (descripción de la instancia) para medir los requerimientos de tiempo de un algoritmo.

El tiempo de ejecución se describe como una función de la entrada T(n)

Ejemplo: T(n)=n2+2n

 COMPLEJIDAD EN EL ESPACIO

La misma idea que se utiliza para medir la complejidad en tiempo de un algoritmo se utiliza para medir su complejidad en espacio. Decir que un programa es O(N) en espacio significa que sus requerimientos de memoria aumentan proporcionalmente con el tamaño del problema. Esto es, si el problema se duplica, se necesita el doble de memoria. Del mismo modo, para un programa de complejidad O ( N2 ) en espacio, la cantidad de memoria que se necesita para almacenar los datos crece con el cuadrado del tamaño del problema: si el problema se duplica, se requiere cuatro veces más memoria. En general, el cálculo de la complejidad en espacio de un algoritmo es un proceso sencillo que se realiza mediante el estudio de las estructuras de datos y su relación con el tamaño del problema.

El problema de eficiencia de un programa se puede plantear como un compromiso entre el tiempo y el espacio utilizados. En general, al aumentar el espacio utilizado para almacenar la información, se puede conseguir un mejor desempeño, y, entre más compactas sean las estructuras de datos, menos veloces resultan los algoritmos. Lo mismo sucede con el tipo de estructura de datos que utilice un programa, puesto que cada una de ellas lleva implícitas unas limitaciones de eficiencia para sus operaciones básicas de administración. Por eso, la etapa de diseño es tan importante dentro del proceso de construcción de software, ya que va a determinar en muchos aspectos la calidad del producto obtenido.

EFICIENCIA DE LOS ALGORITMOS

Con mucha frecuencia se plantea la necesidad de tener que decidir que algoritmo se debe utilizar para resolver un determinado problema, de entre un conjunto de algoritmos posibles. Una estrategia para decidir que algoritmos escoger consistiría en implementar todos estos algoritmos, ejecutarlos, y escoger el mas eficiente. Esta aproximación tiene principalmente dos inconvenientes. Por un lado, es necesario implementar un conjunto de algoritmos, aunque en realidad solo se necesita uno, lo que representa un esfuerzo considerable (generalmente prohibitivo). Por otro lado, el hecho de ejecutar una implementación de un algoritmo en una maquina concreta y por un conjunto de datos de prueba específicos, no necesariamente aporta suficiente información para saber como se comportara el mismo algoritmo en una maquina diferente o con entradas diferentes. Así pues el objetivo consiste en estudiar las propiedades del algoritmo a priori, e implementar solo lo que se considere mejor. La calidad de un algoritmo normalmente se mide en función de su eficiencia, pero también hay que valorar el coste de escribirlo, entenderlo y modificarlo.  

La Eficiencia nos la da el Análisis de Algoritmos:

–  Dimensión Temporal: Medida del tiempo empleado.

–  Dimensión Espacial: medida de los recursos invertidos.

•        Encontrar Algoritmos eficientes puede definir si Existe o no una Solución al Problema.

•        Al Análisis de Algoritmos se centra en el estudio de los Bucles, del cual en última instancia, dependerán las instrucciones a ser ejecutadas.

No se puede realizar un análisis del número de Instrucciones pues son dependientes de las tecnologías (RISK, CISC).

Eficiencia = F(n)

Siendo n la cantidad de elementos a ser procesados

Medición de la Eficiencia:

La estimación debe ser independiente de la plataforma y la Lenguaje con que se codificará pero debe reflejar sus diferencias.

- Usamos el Orden de Magnitud (O­grande) de la Eficiencia del Tiempo y de los recursos.

- Se lo complementa con la Tasa de crecimiento del programa para evaluar su comportamiento Futuro.

 ¿Cómo comparar la Eficiencia Real de 2 Algoritmos?

- Programándolos, implementándolos y midiendo para el mismo lote de Prueba: el tiempo de ejecución y los recursos utilizados.

- Suele ser caro, y una vez realizado no suele ser sencillo volver atrás y corregir.

Análisis de Rendimiento:

Mediante la complejidad en el Tiempo y en el Espacio

Tiempo de Ejecución: dependerá del programa y de su entrada (carga de trabajo).

- El tiempo medio suele ser mas realista. Para usar todos los tipos de entradas son equiprobables.

- El Tiempo Máximo depende de la Carga Máxima: y no siempre se puede establecer con claridad o es estadísticamente variable

Asíntotas:

◦   El análisis de la eficiencia algorítmica nos lleva a estudiar el comportamiento de los algoritmos frente a condiciones extremas. Matemáticamente hablando, cuando N tiende al infinito Y , es un comportamiento asintótico.

◦   Sean g(n) diferentes funciones que determinan el uso de recursos, pudiendo existir infinidad de funciones g.

◦   Estas funciones g serán congregadas en familias, usando como criterio de agrupación su comportamiento asintótico, este comportamiento asintótico es similar cuando los argumentos toman valores muy grandes.

◦   Una familia de funciones que comparten un mismo comportamiento asintótico será llamada un Orden de Complejidad. Estas familias se designan con O( log (n)).

◦   Para cada uno de estos conjuntos se suele identificar un miembro f(n) que se utiliza como representante de la familia, hablándose del conjunto de funciones g que son del orden de f(n).

En resumen:

El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional mas amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes. A la hora de realizar un análisis teórico de algoritmos es conveniente calcular su complejidad en su sentido asintótico, es decir, para un tamaño de entrada suficientemente grande.

Lo esencial de la investigación era hacer hincapié en la complejidad en el tiempo y espacio, así como la eficiencia de los algoritmos. Como ya se menciono anteriormente la complejidad de tiempo es mas que nada el calculo del tiempo que tarda en ejecutarse el algoritmo de igual manera la complejidad de espacio, es la memoria que ocupa dicho algoritmo y por ultimo la eficiencia nos ayuda a saber cuales son las medidas adecuadas a tomar para el uso de estos tipos de algoritmos de acuerdo al problema a resolver.