PDF de programación - Análisis de algoritmos

Análisis de algoritmos.

- Introducción.

- Notaciones asintóticas.

- Ecuaciones de recurrencia.

- Ejemplos.

1

Introducción

• Algoritmo: Conjunto de reglas para resolver un
problema. Su ejecución requiere unos recursos.

Memoria E/S

Comuni-
caciones

0 ó más
entradas

ALGORITMO

1 ó más
salidas

• Un algoritmo es mejor cuantos menos recursos

consuma. Pero....

• Otros criterios: facilidad de programarlo, corto,

fácil de entender, robusto...

2

Introducción

• Criterio empresarial: Maximizar la eficiencia.
• Eficiencia: Relación entre los recursos

consumidos y los productos conseguidos.

• Recursos consumidos:
– Tiempo de ejecución.
– Memoria principal.
– Entradas/salidas a disco.
– Comunicaciones, procesadores,...

• Lo que se consigue:

– Resolver un problema de forma exacta.
– Resolverlo de forma aproximada.
– Resolver algunos casos...

3

Introducción

• Recursos consumidos.

Ejemplo. ¿Cuántos recursos de tiempo y
memoria consume el siguiente algoritmo sencillo?

i:= 0
a[n+1]:= x
repetir

i:= i + 1

hasta a[i] = x

• Respuesta: Depende.
• ¿De qué depende? De lo que valga n y x, de lo

que haya en a, de los tipos de datos, de la
máquina...

4

Introducción

• En general los recursos dependen de:

– Factores externos.

• El ordenador donde lo ejecutemos: 286, Pentium III, Cray,...
• El lenguaje de programación y el compilador usado.
• La implementación que haga el programador del algoritmo. En

particular, de las estructuras de datos utilizadas.

– Tamaño de los datos de entrada.

• Ejemplo. Calcular la media de una matriz de NxM.

– Contenido de los datos de entrada.

• Mejor caso. El contenido favorece una rápida ejecución.
• Peor caso. La ejecución más lenta posible.
• Caso promedio. Media de todos los posibles contenidos.
• Los factores externos no aportan información

sobre el algoritmo.

5

Introducción

• Conclusión: Estudiar la variación del tiempo y la
memoria necesitada por un algoritmo respecto al
tamaño de la entrada y a los posibles casos, de
forma aproximada (y parametrizada).

• Ejemplo. Algoritmo anterior. Conteo de

instrucciones.
– Mejor caso. Se encuentra x en la 1ª posición:

Tiempo(N) = a

– Peor caso. No se encuentra x:

Tiempo(N) = b·N + c

– Caso medio. Se encuentra x con probabilidad P:

Tiempo(N) = b·N + c - (d·N+e)·P

6

Introducción

Normalmente usaremos la notación T(N)=..., pero
¿qué significa T(N)?

• Tiempo de ejecución en segundos. T(N) = bN + c.

– Suponiendo que b y c son constantes, con los segundos

que tardan las operaciones básicas correspondientes.

• Instrucciones ejecutadas por el algoritmo. T(N) =

2N + 4.
– ¿Tardarán todas lo mismo?

• Ejecuciones del bucle principal. T(N) = N+1.

– ¿Cuánto tiempo, cuántas instrucciones,...?

– Sabemos que cada ejecución lleva un tiempo constante,

luego se diferencia en una constante con los anteriores.

7

Introducción

• Asignación de tiempos, para el conteo de

instrucciones. Algunas reglas básicas.
– Operaciones básicas (+, -, *, :=,...): Una unidad de tiempo, o

alguna constante.

– Operaciones de entrada salida: Otra unidad de tiempo, o

una constante diferente.

– Bucles FOR: Se pueden expresar como un sumatorio, con los

límites del FOR.

– IF y CASE: Estudiar lo que puede ocurrir. Mejor caso y peor

caso según la condición. ¿Se puede predecir cuándo se
cumplirán las condiciones?

– Llamadas a procedimientos: Calcular primero los

procedimientos que no llaman a otros.

– Bucles WHILE y REPEAT: Estudiar lo que puede ocurrir.

¿Existe una cota inferior y superior del número de
ejecuciones? ¿Se puede convertir en un FOR?

8

Introducción

• El análisis de algoritmos también puede ser a

posteriori: implementar el algoritmo y contar lo que
tarda para distintas entradas.

• Ejemplo. Programa

“prueba.exe”:
– N= 4, T(4)= 0.1 ms
– N= 5, T(5)= 5 ms
– N= 6, T(6)= 0.2 s
– N= 7, T(7)= 10 s
– N= 8, T(8)= 3.5 min

30

25

20

15

10

5

0

1

2

3

4

5

6

7

8

• ¿Qué conclusiones podemos extraer?
• Análisis a priori: Evitamos la implementación, si el

algoritmo es poco eficiente. Podemos hacer previsiones.
Podemos comparar con otros algoritmos.

9

Notaciones asintóticas

Definiciones

• El tiempo de ejecución T(n) está dado en base a

unas constantes que dependen de factores
externos.

• Nos interesa un análisis que sea independiente de

esos factores.

• Notaciones asintóticas: Indican como crece T,

para valores suficientemente grandes
(asintóticamente) sin considerar constantes.

• O(T): Orden de complejidad de T.

• Ω(T): Orden inferior de T, u omega de T.

• Θ(T): Orden exacto de T.

10

Definiciones

Orden de complejidad de f(n): O(f)

• Dada una función f: N →→→→ R+, llamamos orden de f

al conjunto de todas las funciones de N en R+
acotadas superiormente por un múltiplo real
positivo de f, para valores de n suficientemente
grandes.

O(f)= { t: N → R+ / ∃∃∃∃ c ∈ R+, ∃∃∃∃ n0 ∈ N, ∀∀∀∀ n ≥ n0:

t(n) ≤ c·f(n) }

11

R+

O(f)

Definiciones

c·f(n)

Ojo:
• O(f) es un conjunto de funciones, no una función.
•

“Valores de n sufic. grandes...”: no nos importa lo que pase
para valores pequeños.

N

•

“Funciones acotadas superiormente por un múltiplo de f...”:
nos quitamos las constantes.

• La definición es aplicable a cualquier función de N en R, no

sólo tiempos de ejec.

12

Definiciones

• Uso de los órdenes de complejidad: dado un tiempo t(n),

encontrar la función f más simple tal que t ∈∈∈∈ O(f), y que
más se aproxime asintóticamente.

• Ejemplo. t(n) = 2n2/5 + 3π/2; t(n) ∈ O(n2).

• Relación de orden entre O(..) = Relación de

inclusión entre conjuntos.
– O(f) ≤ O(g) ⇔ O(f) ⊆ O(g) ⇔ Para toda t ∈ O(f), t ∈ O(g)

• Se cumple que:

– O(c) = O(d), siendo c y d constantes positivas.
– O(c) ⊂ O(n)
– O(cn + b) = O(dn + e)
– O(p) = O(q), si p y q son polinomios del mismo grado.
– O(p) ⊂ O(q), si p es un polinomio de menor grado que q.

13

Definiciones

Orden inferior u omega de f(n): ΩΩΩΩ(f)

• Dada una función f: N →→→→ R+, llamamos omega de

f al conjunto de todas las funciones de N en R+
acotadas inferiormente por un múltiplo real
positivo de f, para valores de n suficientemente
grandes.

Ω(f)= { t: N → R+ / ∃∃∃∃ c ∈ R+, ∃∃∃∃ n0 ∈ N, ∀∀∀∀ n ≥ n0:

t(n) ≥ c·f(n) }

• La notación omega se usa para establecer cotas

inferiores del tiempo de ejecución.

• Relación de orden: igual que antes.

14

Definiciones

Orden exacto de f(n): ΘΘΘΘ(f)

• Dada una función f: N →→→→ R+, llamamos orden

exacto de f al conjunto de todas las funciones de
N en R+ que crecen igual que f, asintóticamente y
salvo constantes.

ΘΘΘΘ(f) = O(f) ∩ Ω(f) =

= { t: N → R+ / ∃∃∃∃ c, d ∈ R+, ∃∃∃∃ n0 ∈ N, ∀∀∀∀ n ≥ n0:

c·f(n) ≥ t(n) ≥ d·f(n) }

15

R+

ΘΘΘΘ(f)

Definiciones.

f(n)

N

• Ejemplos. ¿Cuáles son ciertas y cuáles no?
n3 ∈ O(n2)
n3 ∈ Ω(n2)
n3 ∈ Θ(n2)
(2+1)n ∈ Ω(2n)
n2 ∈ O(n!!)

n2 ∈ O(n3)
n2 ∈ Ω(n3)
n2 ∈ Θ(n3)
(2+1)n ∈ O(2n)
(n+1)! ∈ O(n!)

3n2 ∈ O(n2)
3n2 ∈ Ω(n2)
3n2 ∈ Θ(n2)
2n+1 ∈ O(2n)
O(n) ∈ O(n2)

16

Definiciones

Notación o pequeña de f(n): o(f)

• Dada una función f: N →→→→ R+, llamamos o pequeña

de f al conjunto de todas las funciones de N en R+
que crecen igual que f asintóticamente:

o(f)= { t: N → R+ / lim t(n)/f(n) = 1}

n→∞

• Esta notación conserva las constantes

multiplicativas para el término de mayor orden.
• Ejemplo. t(n) = amnm + am-1nm-1 + ... +a1n + a0

t(n) ∈ o(amnm) ≠ o(nm)

• ¿o(amnm) ⊆ O(amnm)? ¿o(t) ⊆ O(t)?

17

• Ejemplos. Estudiar t(n) y expresarlo con O, Ω, Θ y o.

Definiciones

for i:= 1 to N

for j:= 1 to N

suma:= 0
for k:= 1 to N

suma:=suma+a[i,k]*a[k,j]

end

c[i, j]:= suma

end

end

Funcion Fibonacci (N: int): int;
if N<0 then

error(‘No válido’)

case N of

0, 1: return N

else

fnm2=0
fnm1= 1
for i:= 2 to n

fn:= fnm1 + fnm2
fnm2:= fnm1
fnm1:= fn

end
return fn

end

18

Definiciones

• Ejemplos. Estudiar t(n) y expresarlo con O, Ω, Θ y o.
A[0, (n-1) div 2]:= 1
key:= 2
i:= 0
j:= (n-1) div 2
cuadrado:= n*n
while key<=cuadrado do

for i:= 1 to N do
if Impar(i) then

k:= (i-1) mod n
l:= (j-1) mod n
if A[k, l] ≠ 0 then

i:= (i + 1) mod n

else

i:= k
j:= l

end
A[i, j]:= key
key:= key+1

end

for j:= i to n do

x:= x + 1

end
for j:= 1 to i do

y:= y + 1

end

end

end

19

Propiedades de las notaciones asintóticas

• P1. Si f ∈ O(g) y g ∈ O(h) entonces f ∈ O(h).

– Si f ∈ Ω(g) y g ∈ Ω(h) entonces f ∈ Ω(h)
– Ej. 2n+1 ∈ O(n), n ∈ O(n2) ⇒ 2n+1 ∈ O(n2)

• P2. Si f ∈ O(g) entonces O(f) ⊆ O(g).

– ¿Cómo es la relación para los Ω?

• P3. Dadas f y g de N en R+, se cumple:

– i) O(f) = O(g) ⇔ f ∈ O(g) y g ∈ O(f)

– ii) O(f) ⊆ O(g) ⇔ f ∈ O(g)

20

Propiedades de las notaciones asintóticas

• ¿La relación de orden entre O(..) es completa?

Dadas f y g, ¿se cumple O(f)⊆O(g) ó O(g)⊆O(f)?

• P4. Dadas f y g, de N en R+, O(f+g) = O(max(f, g)).

– Ω(f+g) = Ω(max(f+g))

– ¿Y para los Θ(f+g)?
– ¿Es cierto que O(f - g) = O(max(f, -g))?

• P5. Dadas f y g de N en R+, se cumple:

– i) limn→∞ f(n) ∈ R+ ⇒ O(f)=O(g), Ω(f)=Ω(g), Θ(f)=Θ(g)

g(n)

– ii) limn→∞ f(n) = 0 ⇒ O(f) ⊆ O(g), Ω(g) ⊆ Ω(f)

g(n)

21

Propiedades de las notaciones asintóticas

– P5. Ej. ¿Qué relación hay entre O(log2 n) y O(log10 n)?

• P6. Dadas f y g de N en R+, O(f)=O(g) ⇔ Θ(f)=Θ(g)

⇔ f ∈ Θ(g) ⇔ Ω(f)=Ω(g)

• P7. Dadas f y g de N en R+, se cumple:

– i) limn→∞ f(n) ∈ R+ ⇒ f ∈ Θ(g)

g(n)

– ii) limn→∞ f(n) = 0 ⇒ f ∈ O(g), pero no necesariamt f ∈ Θ(g)

g(n)

– iii) limn→∞ f(n) = +∞ ⇒ f ∈ Ω(g), pero no neces. f ∈ Θ(g)

g(n)

22

Notaciones con varios parámetros

• En general, el tiempo y la memoria consumidos

pueden depender de muchos parámetros.

• f: Nm →→→→ R+
• Ej. Memoria en una tabla hash. M(B,n, l, k) = kB+l+n+2kn

(f: Nx...m..xN → R+)

Orden de complejidad de f(n1, n2, ..., nm): O(f)

• Dada una función f: Nm →→→→ R+, llamamos orden de f al
conjunto de todas las funciones de Nm en R+ acotadas
superiormente por un múltiplo real positivo de f, para valores
de (n1, ..., nm) suficientemente grandes.

O(f)= { t: Nm → R+ / ∃∃∃∃ c ∈ R+, ∃∃∃∃ n1, n2, ..,