PDF de programación - Analisis de algoritmos

Analisis de algoritmos
Analisis de algoritmos

Eficiencia
Eficiencia

Es la capacidad de disponer de un
 Es la capacidad de disponer de un
recurso.
recurso.
En el caso de los algoritmos, la
 En el caso de los algoritmos, la
eficiencia se logra haciendo el mejor uso
eficiencia se logra haciendo el mejor uso
posible de los recursos del sistema.
posible de los recursos del sistema.

Recursos
Recursos

¿Qué recursos?
 ¿Qué recursos?
• Tiempo
Tiempo
• Memoria
Memoria
• Medios de almacenamiento secundario
Medios de almacenamiento secundario
• RedRed

Análisis de eficiencia de
Análisis de eficiencia de
algoritmos
algoritmos
Se puede plantear una función
 Se puede plantear una función

Tiempo_de_ejecución(Tamaño_del_problema)
Tiempo_de_ejecución(Tamaño_del_problema)

Uso_de_Recurso_R(Tamaño_del_Problema)
Uso_de_Recurso_R(Tamaño_del_Problema)

que relacione cuanto de un recurso
que relacione cuanto de un recurso
determinado se utiliza con el tamaño del
determinado se utiliza con el tamaño del
problema al cual se aplica.
problema al cual se aplica.
En este caso tomaremos como recurso de
 En este caso tomaremos como recurso de
estudio el tiempo, con lo cual la función
estudio el tiempo, con lo cual la función
sería
sería

Magnitudes: Tamaño del
Magnitudes: Tamaño del
problema
problema
Llamamos n n a la medida del tamaño
a la medida del tamaño
 Llamamos
del problema o de los datos a procesar.
del problema o de los datos a procesar.
Qué es lo que mide nn depende de cada
depende de cada
problema en particular.
problema en particular.
– Ordenamiento:
–
– Determinante de una matriz:

Ordenamiento: nn es la cantidad de elementos a ordenar.
es la cantidad de elementos a ordenar.
Factorial: nn coincide con el operando.
coincide con el operando.
Factorial:
Determinante de una matriz: n n es el orden de la matriz.
es el orden de la matriz.

 Qué es lo que mide

Magnitudes: Tiempo de
Magnitudes: Tiempo de
ejecución
ejecución
o el tiempo de ejecución de un
 T(n)T(n) o el tiempo de ejecución de un

programa en función de su nn se podría:
se podría:
programa en función de su
– Medir físicamente, ejecutando el programa
Medir físicamente, ejecutando el programa
y tomando el tiempo
y tomando el tiempo
– Contando las instrucciones a ejecutar y
Contando las instrucciones a ejecutar y
multiplicando por el tiempo requerido por
multiplicando por el tiempo requerido por
cada instrucción
cada instrucción

pero…pero…

Magnitudes: Tiempo de
Magnitudes: Tiempo de
ejecución
ejecución
 … … los métodos anteriores dependen
los métodos anteriores dependen
del modelo de recursos disponibles y
del modelo de recursos disponibles y
esto imposibilita la comparación con
esto imposibilita la comparación con
otros algoritmos.
otros algoritmos.

Entonces…
Entonces…

Magnitudes: Tiempo de
Magnitudes: Tiempo de
ejecución
ejecución
Se toman como unidad las
 Se toman como unidad las
operaciones elementales: asignación
operaciones elementales: asignación
y comparación.
y comparación.
Luego se puede multiplicar el
 Luego se puede multiplicar el
resultado por el tiempo que llevan
resultado por el tiempo que llevan
estas unidades.
estas unidades.

Ejemplo: mínimo de tres
Ejemplo: mínimo de tres
valores.
valores.
Método 1:
Método 1:

m:= a;
m:= a;
If b<m then m:= b;
If b<m then m:= b;
If c<m then m:= c;
If c<m then m:= c;

Método 2:
Método 2:

If a <= b then
If a <= b then
if a <= c then m:= a
if a <= c then m:= a
else m:= c
else m:= c
Else if b<= c then m:= b
Else if b<= c then m:= b

else m:= c;
else m:= c;

Ejemplo: mínimo de tres
Ejemplo: mínimo de tres
valores.
valores.
Método 3:
Método 3:

If (a<=b)and(a<=c) then m:= a;
If (a<=b)and(a<=c) then m:= a;
If (b<=a)and(b<=c) then m:= b;
If (b<=a)and(b<=c) then m:= b;
If (c<=a)and(c<=b) then m:= c;
If (c<=a)and(c<=b) then m:= c;

Método 4:
Método 4:

If (a <= b)and(a<=c) then
If (a <= b)and(a<=c) then
m:=am:=a
else if b <= c then
else if b <= c then
m:= bm:= b
else m:= c;
else m:= c;

Ejemplo: mínimo de tres
Ejemplo: mínimo de tres
valores.
valores.
– Método 1:
Método 1:
m:= a;
m:= a;
If b<m then m:= b;
If b<m then m:= b;
If c<m then m:= c;
If c<m then m:= c;

– Comparaciones: 2
Comparaciones: 2
–
1 <= Asignaciones <= 3
1 <= Asignaciones <= 3

Ejemplo: mínimo de tres
Ejemplo: mínimo de tres
valores.
valores.
Método 2:
Método 2:

– Comparaciones: 2
Comparaciones: 2
–
Asignaciones: 1
Asignaciones: 1

If a <= b then
If a <= b then
if a <= c then m:= a
if a <= c then m:= a
else m:= c
else m:= c
Else if b<= c then m:= b
Else if b<= c then m:= b

else m:= c;
else m:= c;

Ejemplo: mínimo de tres
Ejemplo: mínimo de tres
valores.
valores.
Método 3:
Método 3:

If (a<=b)and(a<=c) then m:= a;
If (a<=b)and(a<=c) then m:= a;
If (b<=a)and(b<=c) then m:= b;
If (b<=a)and(b<=c) then m:= b;
If (c<=a)and(c<=b) then m:= c;
If (c<=a)and(c<=b) then m:= c;

– Comparaciones: 6
Comparaciones: 6
–
Asignaciones: 1
Asignaciones: 1

Ejemplo: mínimo de tres
Ejemplo: mínimo de tres
valores.
valores.
Método 4:
Método 4:

If (a <= b)and(a<=c) then
If (a <= b)and(a<=c) then
m:=am:=a
else if b <= c then
else if b <= c then
m:= bm:= b
else m:= c;
else m:= c;

– 2 <= Comparaciones <=3
2 <= Comparaciones <=3
–
Asignaciones: 1
Asignaciones: 1

Ejemplo: mínimo de tres
Ejemplo: mínimo de tres
valores.
valores.

¿La diferencia parece poco relevante?
¿La diferencia parece poco relevante?

Ejemplo: mínimo de tres
Ejemplo: mínimo de tres
valores.
valores.
Considere la repetición 500 veces de
Considere la repetición 500 veces de
estas comparaciones: resultan 1000,
estas comparaciones: resultan 1000,
1500 o 3000 comparaciones.
1500 o 3000 comparaciones.

Si por ejemplo tuviera que compararse los 500
Si por ejemplo tuviera que compararse los 500
elementos de tres vectores, determinando para cada ii
elementos de tres vectores, determinando para cada
cuál de los tres es el menor.
cuál de los tres es el menor.

Análisis de algoritmos

Se realiza tomando los siguientes
casos:

– El mejor
– El peor
– El caso promedio

El primero no presenta mayor interés. En
general son más útiles los otros dos.

El caso promedio

 Volvamos sobre el método 4.

If (a <= b)and(a<=c) then
If (a <= b)and(a<=c) then

m:=am:=a

else if b <= c then
else if b <= c then

m:= bm:= b
else m:= c;
else m:= c;

– En el mejor de los casos: 2 comparaciones.
– En el peor de los casos: 3 comparaciones.

El caso promedio

 Examinemos todos los casos

posibles:
– a <= b <= c
– a <= c <= b
– b <= a <= c
– b <= c <= a
– c <= a <= b
– c <= b <= a

2 comparaciones
2 comparaciones
3 comparaciones
3 comparaciones
3 comparaciones
3 comparaciones

Promedio: (2+2+3+3+3+3)/6 = 8/3 (2,66)

Ejemplo: evitar
repetición innecesaria
de cálculos
 Método 1:
T:= x * x * x;
Y:= 0;
For n:= 1 to 2000 do y := y + 1 / (t-n)

 Método 2:

Y:= 0;
For n:= 1 to 2000 do y := y + 1 / (x * x * x - n)

¿Cuál es más eficiente y por qué?

Análisis de algoritmos

 Hay dos maneras de estimar el

tiempo de ejecución:
– Análisis empírico: se mide el tiempo de

respuesta para distintos juegos de
datos.

– Análisis teórico: se calculan el número
de comparaciones y asignaciones que
efectúa el algoritmo.

Análisis de algoritmos

 Si bien las técnicas empíricas son más
sencillas de aplicar presentan algunos
inconvenientes:
– Están afectadas por la potencia del equipo en el que se

– Presentan variaciones según las características de los

mide el tiempo.

datos de entrada

 Cuando es posible, se prefiere el análisis

teórico del algoritmo.

 T(T(nn) es el tiempo de ejecución en el
 TTpromprom((nn) es el valor medio del tiempo de ejecución de
) es el valor medio del tiempo de ejecución de

peor casocaso..

T(T(nn) versus T
) versus Tpromprom(n)(n)
) es el tiempo de ejecución en el peor

todas las entradas de tamaño nn..
todas las entradas de tamaño
Aunque parezca más razonable Tpromprom((nn), puede ser
), puede ser
 Aunque parezca más razonable T
engañoso suponer que todas las entradas son
engañoso suponer que todas las entradas son
igualmente probables.
igualmente probables.
Casi siempre es más difícil calcular Tpromprom((nn), ya que
), ya que
el análisis se hace intratable en matemáticas y la
el análisis se hace intratable en matemáticas y la
noción de entrada promedio
puede carecer de un
noción de entrada
promedio puede carecer de un
significado claro.
significado claro.

 Casi siempre es más difícil calcular T

Asíntotas
Asíntotas

Los problemas pequeños en general se pueden
 Los problemas pequeños en general se pueden
resolver de cualquier forma.
resolver de cualquier forma.
En cambio son los problemas grandes los que
 En cambio son los problemas grandes los que
plantean desafíos y requieren de la
plantean desafíos y requieren de la
administración cuidadosa de los recursos.
administración cuidadosa de los recursos.
Estudiaremos entonces el comportamiento
comportamiento
de los algoritmos, es decir qué sucede
asintótico de los algoritmos, es decir qué sucede
asintótico
con los mismos cuando nn tiende a infinito.
tiende a infinito.
con los mismos cuando

 Estudiaremos entonces el

Notación asintótica OO
Notación asintótica

Para hacer referencia a la velocidad
Para hacer referencia a la velocidad
de crecimiento de una función se
de crecimiento de una función se
puede utilizar la notación asintótica
notación asintótica
puede utilizar la
u u OO (“o mayúscula) y que señala que
(“o mayúscula) y que señala que
función se comporta como “techo”
función se comporta como “techo”
de crecimiento o cota superior de la
de crecimiento o cota superior de la
primera.
primera.

Notación asintótica OO
Notación asintótica

O n2

Por ejemplo, si se describe que el tiempo de
Por ejemplo, si se describe que el tiempo de
ejecución T(n)T(n) de un programa es

de un programa es
ejecución

(se lee “o mayúscula de n al cuadra