Clase 1 Fundamentos de analisis de algoritmos

UNIDAD I
Fundamentos de Análisis de
Algoritmos

Programación III.
[Programación III ]- [1]

Fundamentos de Análisis de algoritmos
o 

Una vez se disponga de un algoritmo que funcione
correctamente, es necesario definir criterios para
medir su rendimiento o comportamiento. Estos
criterios se centran principalmente en su
simplicidad y en el uso eficiente de los recursos.

[2]

Teoría de laComplejidad
o 

o 

La complejidad de un algoritmo hace referencia a la
cantidad de tiempo y espacio necesarios para
ejecutar el algoritmo.
Con la tecnología actual se puede decir que la
memoria de las computadoras es abundante y
barata, es por eso la complejidad del algoritmo se
puede limitar al tiempo de ejecución del algoritmo.

[3]

o 

El uso eficiente de los recursos, suele medirse en
funciónde dos parámetros:
n  el

espacio, es decir, memoria que utiliza,
n  y el tiempo, lo que tarda en ejecutarse.

[4]

o 

El tiempo de ejecución de un algoritmo va a
depender de diversos factores como son: los datos
de entrada que se le suministren, la calidad del
código generado por el compilador para crear el
programa objeto, la naturaleza y rapidez de las
instrucciones máquina del procesadorconcreto que
ejecute el programa, y la complejidad intrínseca
del algoritmo.

[5]

o 

o 

Ambas medidas son importantes puesto que, si bien
la primera ofrece estimaciones del comportamiento
de los algoritmos de forma independiente de la
computadora en donde serán implementados y sin
necesidad de ejecutarlos, la segunda representa las
medidas reales del comportamiento del algoritmo.
Estasmedidas son funciones temporales de los
datos de entrada.

[6]

TIEMPO DE EJECUCIÓN
o 

El tiempo de ejecución de un algoritmo es una
función que mide el número de operaciones
elementales que realiza el algoritmo para un tamaño
de entrada dado.

[7]

o 

A la hora de medir el tiempo, siempre se hará en
función del número de operaciones elementales
que realiza dicho algoritmo, entendiendo poroperaciones elementales (OE) aquellas que la
computadora realiza en tiempo acotado por una
constante.

[8]

Operaciones Elementales - OE
o 

Las operaciones aritméticas básicas, asignaciones
a variables de tipo predefinido por el compilador,
los saltos (llamadas a funciones y procedimientos,
retorno desde ellos), las comparaciones lógicas y
el acceso a estructuras indexadas básicas, como
son losvectores y matrices. Cada una de ellas
contabilizará como 1 OE.

[9]

Ejemplo

[10]

Calcule el OE para cada línea de código

[11]

Análisis: Mejor Escenario
o 

Se efectuará la línea (1) y de la línea (2) sólo la
primera mitad de la condición, que supone 2 OE
(suponemos que las expresiones se evalúan con
“cortocircuito”, es decir, una expresión lógica deja
de ser evaluada en el momento que seconoce su
valor, aunque no hayan sido evaluados todos sus
términos). Tras ellas la función acaba ejecutando
las líneas (4) a (6). En consecuencia,

T(n)=1+2+3=6.
[12]

Análisis: Peor Escenario
o 

Se efectúa la línea (1), el bucle se repite n–1 veces
hasta que se cumple la segunda condición, después
se efectúa la condición de la línea (5) y la función
acaba al ejecutarse la línea (7). Cadaiteración del
bucle está compuesta por las líneas (2) y (3), junto
con una ejecución adicional de la línea (2) que es la
que ocasiona la salida del bucle.

[13]

Análisis: Escenario Medio
o 

o 

El bucle se ejecutará un número de veces entre 0 y
n–1, y vamos a suponer que cada una de ellas tiene
la misma probabilidad de suceder.
Como existen n posibilidades (puede que el número
buscado no esté) portanto cada una tendrá una
probabilidad asociada de 1/n.

[14]

Asíntotas
o 

o 

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, es un
comportamiento asintótico.
Entiéndase N como el tamaño de entradas

[15]

Notación O (Omicrón, cota superior)
o 

Dada una...