Unidad VII: Anlisis de algoritmos

Unidad VII: Anlisis de algoritmos

Concepto de complejidad de algoritmos.

Como se puede apreciar en las grficas, entre mayor se al nmero de datos mayor tiempo se aplica en las grficas a), b) y c), lo cual no ocurre con la grfica d), por lo tanto podemos deducir que una funcin que se acerque ms al eje de las x es ms constante y eficiente en el manejo de grandes cantidades de datos.Aritmtica de la notacin O.La notacin asinttica O (grande) se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una funcin, es decir, su utilidad radica en encontrar un lmite superior del tiempo de ejecucin de un algoritmo buscando el peor caso.

La definicin de esta notacin es la siguiente: f(n) y g(n) funciones que representan enteros no negativos a nmeros reales. Se dice que f(n) es O(g(n)) si y solo si hay una constante real c>0 y un entero constante n0>=1 tal que f(n)= n0. Esta definicin se ilustra en la figura 1.2.

Complejidad.Tiempo de ejecucin de un algoritmo.

El tiempo de ejecucin de un algoritmo, se refiere a la suma de los tiempos en los que el programa tarda en ejecutar una a una todas sus instrucciones, tomando en cuenta que cada instruccin requiere una unidad de tiempo, dicho tiempo se puede calcular en funcin de n (el nmero de datos), lo que se denomina T(n)

Para este ejemplo se pueden encontrar dos frmulas que determinen el tiempo de ejecucin, la primera representa el peor de los casos y la segunda el mejor de los casos. public int Mayor(){ int may=arr[0]; for(ind=0; indmay) may=arr[ind]; return may;}

Evaluacin y seleccin de algoritmos eficientes

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 consistira en implementar todos estos algoritmos, ejecutarlos, y escoger el ms eficiente.

Esta aproximacin 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 implementacin de un algoritmo en una maquina concreta y por un conjunto de datos de prueba especficos, no necesariamente aporta suficiente informacin para saber cmo 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 funcin de su eficiencia, pero tambin hay que valorar el coste de escribirlo, entenderlo y modificarlo.

Medicin de la Eficiencia:

La estimacin debe ser independiente de la plataforma y la Lenguaje con que se codificar pero debe reflejar sus diferencias.- Usamos el Orden de Magnitud (Ogrande) de la Eficiencia del Tiempo y de los recursos.- Se lo complementa con la Tasa de crecimiento del programa para evaluar su comportamiento Futuro. Cmo comparar la Eficiencia Real de 2 Algoritmos?Programndolos, implementndolos y midiendo para el mismo lote de Prueba: el tiempo de ejecucin y los recursos utilizados.Suele ser caro, y una vez realizado no suele ser sencillo volver atrs y corregir

Medicin de la Eficiencia:

La estimacin debe ser independiente de la plataforma y la Lenguaje con que se codificar pero debe reflejar sus diferencias.- Usamos el Orden de Magnitud (Ogrande) de la Eficiencia del Tiempo y de los recursos.- Se lo complementa con la Tasa de crecimiento del programa para evaluar su comportamiento Futuro. Cmo comparar la Eficiencia Real de 2 Algoritmos?- Programndolos, implementndolos y midiendo para el mismo lote de Prueba: el tiempo de ejecucin y los recursos utilizados.- Suele ser caro, y una vez realizado no suele ser sencillo volver atrs y corregir.

Anlisis de Rendimiento:

Mediante la complejidad en el Tiempo y en el Espacio Tiempo de Ejecucin: depender del programa y de su entrada (carga de trabajo).- El tiempo medio suele ser ms realista. Para usar todos los tipos de entradas son probables.- El Tiempo Mximo depende de la Carga Mxima: y no siempre se puede establecer con claridad o es estadsticamente variableAsntotas:

El anlisis de la eficiencia algortmica nos lleva a estudiar el comportamiento de los algoritmos frente a condiciones extremas. Matemticamente hablando, cuando N tiende al infinito Y, es un comportamiento asinttico.Sean g(n) diferentes funciones que determinan el uso de recursos, pudiendo existir infinidad de funciones g