PDF de programación - Análisis y Diseño de Algoritmos - La eficiencia de los algoritmos

La eficiencia de los algoritmos
La eficiencia de los algoritmos
Análisis y Diseño de Algoritmos
Análisis y Diseño de Algoritmos

La eficiencia de los algoritmos
La eficiencia de los algoritmos

Comparación de algoritmos
 Comparación de algoritmos
 Principio de invarianza
Principio de invarianza
Eficiencia
 Eficiencia
Notaciones asintóticas
 Notaciones asintóticas
 Cálculo de la eficiencia de un algoritmo
 Cálculo de la eficiencia de un algoritmo
Cálculo de la eficiencia de un algoritmo
Cálculo de la eficiencia de un algoritmo
Resolución de recurrencias:
 Resolución de recurrencias:
Método de la ecuación característica
Método de la ecuación característica
Recurrencias homogéneas
 Recurrencias homogéneas
 Recurrencias no homogéneas
Recurrencias no homogéneas
Cambios de variable
 Cambios de variable
 Transformaciones del rango
Transformaciones del rango
 Apéndice: Fórmulas útiles
Apéndice: Fórmulas útiles

11

Comparación de algoritmos
Comparación de algoritmos

A menudo dispondremos de más de un algoritmo para
A menudo dispondremos de más de un algoritmo para
resolver un problema dado, ¿con cuál nos quedamos?
resolver un problema dado, ¿con cuál nos quedamos?

USO DE RECURSOS
USO DE RECURSOS

 Computacionales:
Computacionales:

 Tiempo de ejecución
Tiempo de ejecución
 Espacio en memoria
Espacio en memoria

 No computacionales:
No computacionales:

 Esfuerzo de desarrollo (análisis, diseño & implementación)
Esfuerzo de desarrollo (análisis, diseño & implementación)

22

Comparación de algoritmos
Comparación de algoritmos

Factores que influyen en el uso de recursos
Factores que influyen en el uso de recursos

 Recursos computacionales:
Recursos computacionales:

Diseño del algoritmo
 Diseño del algoritmo
 Complejidad del problema (p.ej. tamaño de las entradas)
Complejidad del problema (p.ej. tamaño de las entradas)
Hardware (arquitectura, MHz, MBs…)
 Hardware (arquitectura, MHz, MBs…)
Hardware (arquitectura, MHz, MBs…)
Hardware (arquitectura, MHz, MBs…)
Calidad del código
 Calidad del código
 Calidad del compilador (optimizaciones)
Calidad del compilador (optimizaciones)

 Recursos no computacionales:
Recursos no computacionales:

Complejidad del algoritmo
 Complejidad del algoritmo
 Disponibilidad de bibliotecas reutilizables
Disponibilidad de bibliotecas reutilizables

33

Principio de invarianza
Principio de invarianza

 Dos implementaciones de un mismo algoritmo no
Dos implementaciones de un mismo algoritmo no
diferirán más que en una constante multiplicativa.
diferirán más que en una constante multiplicativa.

 Si tSi t11(n) y t

(n) y t22(n) son los tiempos de dos
(n) son los tiempos de dos

implementaciones de un mismo algoritmo,
implementaciones de un mismo algoritmo,
implementaciones de un mismo algoritmo,
implementaciones de un mismo algoritmo,
se puede comprobar que:
se puede comprobar que:

∃
dc
,

ℜ∈
,

)(
nt
1

≤

ct

2

(

n

);

)(
nt
2

≤

ndt
)(

1

44

Eficiencia
Eficiencia

Medida del uso de los recursos computacionales
Medida del uso de los recursos computacionales
requeridos por la ejecución de un algoritmo en función
requeridos por la ejecución de un algoritmo en función
del tamaño de las entradas.
del tamaño de las entradas.
del tamaño de las entradas.
del tamaño de las entradas.

T(n)T(n)

Tiempo empleado para ejecutar el
Tiempo empleado para ejecutar el
algoritmo con una entrada de tamaño n
algoritmo con una entrada de tamaño n

55

Eficiencia
Eficiencia

Tipos de análisis
Tipos de análisis
¿Cómo medimos el tiempo de ejecución de un algoritmo?
¿Cómo medimos el tiempo de ejecución de un algoritmo?

Mejor caso
 Mejor caso
En condiciones óptimas (no se usa por ser demasiado optimista).
En condiciones óptimas (no se usa por ser demasiado optimista).
En condiciones óptimas (no se usa por ser demasiado optimista).
En condiciones óptimas (no se usa por ser demasiado optimista).
 Peor caso
Peor caso
En el peor escenario posible (nos permite acotar el tiempo de ejecución).
En el peor escenario posible (nos permite acotar el tiempo de ejecución).
Caso promedio
 Caso promedio
Caso difícil de caracterizar en la práctica.
Caso difícil de caracterizar en la práctica.
Análisis probabilístico
 Análisis probabilístico
Asume una distribución de probabilidad sobre las posibles entradas.
Asume una distribución de probabilidad sobre las posibles entradas.
Análisis amortizado
 Análisis amortizado
Tiempo medio de ejecución por operación
sobre una secuencia de ejecuciones sucesivas.

66

Eficiencia
Eficiencia

Ejemplo
Ejemplo

 Algoritmo 1:
Algoritmo 1:

 Algoritmo 2:
Algoritmo 2:

T(n) = 10
T(n) = 10--44 22nn segundos
segundos
n = 38 datos
n = 38 datos
T(n) = 1 año
T(n) = 1 año
T(n) = 1 año
T(n) = 1 año

T(n) = 10--22 nn33 segundos
T(n) = 10
segundos
n = 1000 bits
n = 1000 bits
T(n) = 1 año
T(n) = 1 año

¿Cuál es mejor? Se precisa un análisis asintótico
¿Cuál es mejor? Se precisa un
análisis asintótico

77

Notaciones asintóticas
Notaciones asintóticas

Estudian el comportamiento del algoritmo cuando el
Estudian el comportamiento del algoritmo cuando el
tamaño de las entradas es lo suficientemente grande,
tamaño de las entradas es lo suficientemente grande,
sin tener en cuenta lo que ocurre para entradas
sin tener en cuenta lo que ocurre para entradas
sin tener en cuenta lo que ocurre para entradas
sin tener en cuenta lo que ocurre para entradas
pequeñas y obviando factores constantes.
pequeñas y obviando factores constantes.

Notaciones asintóticas
Notaciones asintóticas

Orden de eficiencia
Orden de eficiencia

Un algoritmo tiene un tiempo de ejecución de orden
orden
Un algoritmo tiene un
f(n)
f(n), para una función dada
, para una función dada ff, si existe una constante
, si existe una constante
positiva
positiva cc y una implementación del algoritmo capaz
positiva
positiva cc y una implementación del algoritmo capaz
y una implementación del algoritmo capaz
y una implementación del algoritmo capaz
de resolver cada caso del problema en un tiempo
de resolver cada caso del problema en un
tiempo
acotado superiormente por
acotado superiormente por c·f c·f (n)(n), donde
, donde nnes el
es el
tamaño del problema considerado.
tamaño del problema considerado.

88

99

Notaciones asintóticas
Notaciones asintóticas

Notación O
Notación O

Decimos que una función T(n) es O(f(n))
T(n) es O(f(n))
Decimos que una función

si existen constantes n
si existen constantes n00 y c y c
cf(n) para todo n

T(n) ≤≤ cf(n)

para todo n ≥≥ nn00::

tales que
tales que T(n)

T(n) es O(f(n))
T(n) es O(f(n)) ⇔⇔⇔⇔⇔⇔⇔⇔

∃∃∃∃∃∃∃∃cc∈∈∈∈∈∈∈∈R, R, ∃∃∃∃∃∃∃∃nn00∈∈∈∈∈∈∈∈N, tal que

N, tal que ∀∀∀∀∀∀∀∀n>nn>n00∈∈∈∈∈∈∈∈N, T(n)

N, T(n) ≤≤≤≤≤≤≤≤ cf(n)
cf(n)

Notaciones asintóticas
Notaciones asintóticas

Ejemplos
Ejemplos
T(n) = 3n
T(n) = 3n
 T(n)

T(n) eses O(n), O(n log n), O(n

O(n), O(n log n), O(n22), O(n

), O(n33) y O(2

) y O(2nn).).

T(n) = (n+1)2

), O(n33) y O(2
), O(n33) y O(2

 T(n)
 T(n)
 T(n) no

T(n) eses O(nO(n22), O(n
T(n) eses O(nO(n22), O(n
) y O(2nn).).
) y O(2nn).).
O(n log n).
T(n) no eses O(n) O(n) nini O(n log n).
(n) = 32n22 + 17n + 32.
T(n) = 32n2 + 17n + 32(n) = 32n
+ 17n + 32.

 T(n)

T(n) eses O(nO(n22) ) peropero no no eses O(n).O(n).

T(n) = 3n3 + 345n2

 T(n)
T(n) = 3n
 T(n)

T(n) eses O(nO(n33) ) peropero no no eses O(nO(n22).).

T(n) eses O(3O(3nn) ) peropero no no eses O(2O(2nn).).

1010

1111

Notaciones asintóticas
Notaciones asintóticas

Notaciones
Notaciones ΩΩΩΩΩΩΩΩ y y ΘΘΘΘΘΘΘΘ

Notación ΩΩΩΩΩΩΩΩ (cota inferior)
Notación
(cota inferior)

T(n) es ΩΩ(f(n)) cuando
T(n) es
T(n) es
T(n) es ΩΩ(f(n)) cuando
(f(n)) cuando
(f(n)) cuando
∃∃cc∈∈RR++, , ∃∃nn00∈∈N: N: ∀∀nn≥≥nn0 0 ⇒⇒ T(n)

T(n) ≥≥ cfcf(n)(n)

Notación ΘΘΘΘΘΘΘΘ (orden exacto)
Notación
(orden exacto)

T(n) es ΘΘ(f(n)) cuando
T(n) es
(f(n)) cuando
T(n) es O(f(n)) y T(n) es ΩΩ(f(n))
T(n) es O(f(n)) y T(n) es
(f(n))

1212

Órdenes de eficiencia
Órdenes de eficiencia

Órdenes de eficiencia más habituales
Órdenes de eficiencia más habituales

N

O(log2 n)

O(n2)

O(n log2 n)

O(n2)

10
25
50
50
100
1000
10000
100000
1000000

3 µs
5 µs
6 µs
6 µs
7 µs
10 µs
13 µs
17 µs
20 µs

10 µs
25 µs
50 µs
50 µs
100 µs
1 ms
10 ms
100 ms

1 s

30 µs
0.1 ms
0.3 ms
0.3 ms
0.7 ms
10 ms
0.1 s
1.7 s
20 s

0.1 ms
0.6 ms
2.5 ms
2.5 ms
10 ms

1 s
100 s
3 horas
12 días

O(2n)

1 ms
33 s

36 años
36 años
1017 años

…
…
…
…

O(n!)

4 s

1011 años

…
…
…
…
…
…
…

Tiempos calculados suponiendo 1 µs por operación elemental.
O(1)
O(1) ⊂⊂⊂⊂⊂⊂⊂⊂ O(log n)

O(n) ⊂⊂⊂⊂⊂⊂⊂⊂ O(n log n)

O(log n) ⊂⊂⊂⊂⊂⊂⊂⊂ O(n)

O(n log n) ⊂⊂⊂⊂⊂⊂⊂⊂ O(nO(n22)) ⊂⊂⊂⊂⊂⊂⊂⊂ O(nO(n33) ) ⊂⊂⊂⊂⊂⊂⊂⊂ O(2O(2nn) ) ⊂⊂⊂⊂⊂⊂⊂⊂ O(n!)O(n!)

1313

Órdenes de eficiencia
Órdenes de eficiencia

Orden lineal: O(n)
Orden lineal: O(n)
Tiempo de ejecución proporcional al tamaño de la entrada.
Tiempo de ejecución proporcional al tamaño de la entrada.

Ejemplo: Calcular el máximo de n números
Ejemplo: Calcular el máximo de n números a1, …, an.
Ejemplo: Calcular el máximo de n números
Ejemplo: Calcular el máximo de n números a1, …, an.

max ←←←← a1
for i = 2 to n {
if (ai > max)

max ←←←← ai

}

Órdenes de eficiencia
Órdenes de eficiencia

Orden cuadrático: O(n
Orden cuadrático: O(n22))

Aparece cuando tenemos que enumerar todas las
Aparece cuando tenemos que enumerar todas las
parejas posibles de elementos de un conjunto.
parejas posibles de elementos de un conjunto.

Ejemplo: Dado un conjunto de puntos en el plano
Ejemplo: Dado un conjunto de puntos en el plano (x1, y1), …,
Ejemplo: Dado un conjunto de puntos en el plano
Ejemplo: Dado un conjunto de puntos en el plano (x1, y1), …,
(xn, yn), encontrar la pareja más cercana.
encontrar la pareja más cercana.

min ←←←← (x1 - x2)2 + (y1 - y2)2
for i = 1 to n {

for j = i+1 to n {

d ←←←← (xi - xj)2 + (yi - yj)2
if (d < min)

min ←←←← d

}

}

1414

1515

Órdenes de eficiencia
Órdenes de eficiencia

Órdenes O(log n) y O(n log n)