Análisis y Diseño de Algoritmos
Tiempo de Ejecución
Arturo Díaz Pérez
Sección de Computación
Departamento de Ingeniería Eléctrica
CINVESTAV-IPN
Av. Instituto Politécnico Nacional No. 2508
Col. San Pedro Zacatenco
México, D. F. CP 07300
Tel. 5061 3800 Ext. 6562, 6660
e-mail:
[email protected]
Análisis y Diseño de Algoritmos
TimeAnalysis-1
Midiendo el Tiempo de Ejecución
F Benchmarking
Benchmarks: una colección de entradas típicas representativas
de una carga de trabajo para un programa
F Profiling
Asociar a cada instrucción de un programa un número que
representa la fracción del tiempo total tomada para ejecutar esa
instrucción particular
Regla del 90-10
/Regla informal que afirma que el 90% del tiempo de
ejecución se invierte en el 10% del código
Análisis y Diseño de Algoritmos
TimeAnalysis-2
1
Midiendo el Tiempo de Ejecución
F Análisis
Agrupar las entradas de acuerdo a su tamaño, n, y estimar el
tiempo de ejecución del programa en entradas de ese tamaño,
T(n)
Análisis y Diseño de Algoritmos
TimeAnalysis-3
El Problema de Ordenamiento
Entrada: una secuencia de números
<a1, a2, ..., an>
Salida: una permutación de la secuencia
tal que,
F Ejemplo:
3
2
25
1
Análisis y Diseño de Algoritmos
<a’1, a’2, ..., a’n>
a’1= a’2 = ... = a’n
12
3
19
6
2
9
1
12
9
19
6
25
TimeAnalysis-4
2
Método de Inserción
void Inserción( int A[], int n )
{
int i,j;
for( i=1; i < n; i++ ) {
j:= i;
while( j > 0 && A[j] < A[j-1] ) {
Intercambia( &A[j], &A[j-1] );
j--
}
}
}
A:
ordenado
Análisis y Diseño de Algoritmos
llave
TimeAnalysis-5
Método de Inserción: Ejemplo
25
3
12
19
2
1
9
6
3
3
3
2
1
1
1
25
12
12
12
3
2
2
2
25
19
19
12
25
19
2
25
1
3
3
3
12
19
25
9
9
6
12 19
25
6
9
12 19
25
Análisis y Diseño de Algoritmos
TimeAnalysis-6
3
La Entrada del Problema
FTiempo de Ejecución
Debe ser definido como una función de la
entrada
/ Tp = f(E)
Con frecuencia el tiempo de ejecución
depende del tamaño de la entrada
/T(n): El
tiempo de ejecución de un
programa en entradas de tamaño n
3Ejemplo: T(n) = c n2, para alguna constante c
Análisis y Diseño de Algoritmos
TimeAnalysis-7
Tipos de Análisis
F El tiempo de ejecución del peor caso, Tw(n)
El máximo de los tiempos de ejecución sobre todas las entradas de
tamaño n
Puede no ser muy fiel
F El tiempo promedio de ejecución: Ta(n)
El promedio de los tiempos de ejecución sobre todas las entradas de
tamaño n
Puede ser más fiel
En algunas ocasiones puede ser difícil de determinar
F El tiempo de ejecución del mejor caso: Tb(n)
El menor de los tiempos de ejecución sobre todas las entradas de
tamaño n
Puede ser engañoso en un algoritmo lento que trabaja rápido sobre
algunas entradas
Análisis y Diseño de Algoritmos
TimeAnalysis-8
4
Tiempo independiente de la computadora
F El tiempo de ejecución no debe ser expresado en
unidades de tiempo estándar
F ¿Qué significa el tiempo del peor caso para el método
de inserción?
Depende de la velocidad de una computadora
/Velocidad relativa (en la misma computadora)
/Velocidad absoluta (en computadoras diferentes)
F Ignore las constantes dependientes de la computadora
F Observe el crecimiento de T(n) conforme n ? a .
/El tiempo de ejecución de un algoritmo es proporcional a f(n)
Análisis Asintótico
Análisis y Diseño de Algoritmos
TimeAnalysis-9
Comparando Tiempos de Ejecución
T(n)
3000
2000
1000
2n
n / 23
5n2
100n
5
10
15
20
n
Running Time
T(n)
100 n
5n2
n / 23
2n
Análisis y Diseño de Algoritmos
Max. Problem Size
for 10 sec
3
Max. Problem Size
for 10 sec
4
10
14
12
10
100
45
27
13
Increase in Max.
Problem Size
10.0
3.2
2.3
1.3
TimeAnalysis-10
5
Función de Complejidad
F Definición:
Una función de complejidad puede ser cualquier función de los
enteros no negativos a los reales no negativos
f: N fi R‡ 0
F Ejemplos:
f (n ) = n
f (n ) = n2
f (n ) = log n
f (n ) = 3n + 4n2
Análisis y Diseño de Algoritmos
TimeAnalysis-11
Ordenes de Crecimiento
F Dada f: N fi
R, una función con valores no negativos
O ( f (n) ) = { g: N fi R ‡ 0 | $ c > 0 y N0 ˛ N: (n ‡ N0
g(n) £ c * f (n)) }
( f (n) ) = { g: N fi R ‡ 0 | [g ˛ O(f)]
[f ˛ O(g)] }
( f (n) ) = { g: N fi R ‡ 0 | $ c > 0 y N0 ˛ N: (n ‡ N0
f(n) £ c * g (n)) }
Análisis y Diseño de Algoritmos
TimeAnalysis-12
6
Q
W
Ordenes de Crecimiento
F Se escribe g(n) =
( f (n) ) en lugar de g ˛
( f )
F El crecimiento de g está dominado por el de f, si y solo
si, g(n) = O( f (n) )
F g y f poseen el mismo orden de crecimiento, si y solo si,
g(n) = Q
( f (n) )
F El crecimiento de g es al menos el de f, si y solo si, g(n)
= W ( f (n) )
Análisis y Diseño de Algoritmos
TimeAnalysis-13
O( f(n) ): De orden f (n)
n2 + 10 n es O(n2) ¿Por qué?
2 n2
Tome c = 2 y N = 10
n2 + 10 n
10
Análisis y Diseño de Algoritmos
TimeAnalysis-14
7
Cota Superior Asintótica: O
c * f (n)
g (n)
N0
g(n) = O ( f ( n ))
Análisis y Diseño de Algoritmos
TimeAnalysis-15
O: Ejemplos
F ¿1,000,000n2 es O(n2)?
F ¿(n - 1)n / 2 es O(n2)?
F ¿n / 2 es O(n2)?
F ¿log (n 1000000) es O(n)?
F ¿n2 es O(n)?
Análisis y Diseño de Algoritmos
TimeAnalysis-16
8
Cota Inferior Asintótica: W
g (n)
c * f (n)
Análisis y Diseño de Algoritmos
TimeAnalysis-17
N0
g(n) = W
( f ( n ) )
W: Ejemplos
F ¿1,000,000 n2 es W
(n2)?
F ¿(n - 1)n / 2 es W
(n2)?
F ¿n / 2 es W
(n2)?
F ¿log (n 1000000) es W
(n)?
F ¿n2 es W
(n)?
Análisis y Diseño de Algoritmos
TimeAnalysis-18
9
: Mismo Orden de Crecimiento
c * f (n)
g (n)
d * f (n)
g(n) = Q
( f ( n ))
N0
Análisis y Diseño de Algoritmos
TimeAnalysis-19
Q: Ejemplos
F ¿1,000,000 n es Q
(n2)?
F ¿(n - 1)n / 2 es Q
(n2)?
F ¿n / 2 es Q
(n2)?
F ¿log (n 1000000) es Q
(n)?
F ¿n2 es Q
(n)?
Análisis y Diseño de Algoritmos
TimeAnalysis-20
10
Q
Observaciones
F Para cualesquiera f, g: N fi R :
g(n) = O( f (n) )
f(n) = W
( g(n) )
g(n) = Q
( f (n) )
[g(n) = O( f (n) )]
[g(n) = W
( f (n) )]
Análisis y Diseño de Algoritmos
TimeAnalysis-21
Observaciones
F También se define
(n)) }
o( f (n) ) = { g: N fi R ‡ 0 | " c > 0, $ N0 ˛ N: (n ‡ N0
g(n) £ c * f
w( f (n) ) = { g: N fi R ‡ 0 | f ˛ o(g(n)) }
esto es,
/g(n) = o( f (n) )
/g(n) = w( f (n) )
lim
n
)(
ng
)(
nf
=
0
lim
n
)(
ng
)(
nf
+¥=
Análisis y Diseño de Algoritmos
TimeAnalysis-22
11
¥
fi
¥
fi
Propiedades
F Transitividad:
˛ {O, Q
, W
, o, w}:
g(n) =
( f (n) )
f(n) = (h(n)) g(n) =
( h(n) )
F Reflexividad:
f(n) =
( f (n) )
˛ {O, Q
, W }:
F Simetría:
g(n) = Q
Por lo tanto, g(n) = Q
( f (n) )
f(n) = Q
( g(n) )
( f (n) ) define una relación de
equivalencia en el espacio de funciones
Análisis y Diseño de Algoritmos
TimeAnalysis-23
Propiedades
F Simetría transpuesta:
f (n) = O(g(n )), si y solo si, g (n) = W
(f (n ))
f (n) = O(g(n )), si y solo si, g (n) = w
(f (n ))
Análisis y Diseño de Algoritmos
TimeAnalysis-24
12
"
"
Diferencia entre O y o
O ( f (n) ) = {g: N fi R ‡ 0 | : existen constantes positivas c and
N0 tal que g( n) £ c * f (n ) para toda n ‡ N0 }
o ( f (n) ) = {g: N fi R ‡ 0 | : para toda constante positiva c
existe una constante Nc > 0, tal que, g( n) £ c * f (n ) para
toda n ‡ Nc }
Para o la desigualdad se mantiene para todas las constantes
positivas
Mientras que para O la desigualdad se mantiene para algunas
constantes positivas
Análisis y Diseño de Algoritmos
TimeAnalysis-25
Analogía con los Números Reales
F f (n) = O( g(n))
F f (n) = W
( g(n))
»
F f (n) = Q
( g(n))
F f (n) = o
( g(n))
F f (n) = w
( g(n))
a £ b
a ‡ b
a = b
a < b
a > b
Análisis y Diseño de Algoritmos
TimeAnalysis-26
13
»
»
»
»
Observaciones
F A diferencia de los números reales NO todas las
funciones son asintóticamente comparables
Ejemplo: n 1+ sin n y n
F El conjunto o(f (n)) NO es el mismo que el conjunto
O(f (n)) - W
(f (n))
Ejemplo:
)(
ng
=
n
1
es si
es si
n
n
par
impar
Análisis y Diseño de Algoritmos
TimeAnalysis-27
Observaciones
F Los límites se pueden usar para determinar el orden
lim
n
)(
ng
)(
nf
=
c
0
entonces,
entonces,
entonces,
c
)(
(
si ))
O ng
f (n
)(
))
(
(
ng
nf
o
)(
(
(
))
o
nf
ng
=
=
=
>
0
Análisis y Diseño de Algoritmos
TimeAnalysis-28
14
¥
¥
fi
Big O Revisada
T(n) es un O(f(n)), leído como “O de f(n)”, si existe una
constante positiva c y n0, tales que, T(n) £ cf(n) para todo n ‡
n0
Factores constantes “no importan”
/Para cualquier constante positiva d y cualquier función T(n), T(n) es
O(dT(n))
/Si T(n) es O(f(n)), entonces, T(n) es O(df(n)) para cualquier d > 0
Términos de orden inferior “no importan”
/Si T(n) es un polinomio de la forma aknk + ak-1nk-1 + . . . + a1n + a0, tal
que, ak > 0, entonces, T(n) es O(nk)
Análisis y Diseño de Algoritmos
TimeAnalysis-29
Big O Revisada
Si p(n) son q(n) y son polinomios y el grado de q(n) es mayor o
igual al grado de p(n), entonces, p(n) es O(q(n))
p(n) es O(an), exponenciales, an, a > 1, crecen más rápido que
cualquier polinomio, p(n)
f(n) es una cota O ajustada de T(n) si
/T(n) es O(f(n))
/Si T(n) es O(g(n)), entonces, f(n) es O(g(n))
Análisis y Diseño de Algoritmos
TimeAnalysis-30
15
Re
Comentarios de: Tiempo de Ejecución - Análisis y Diseño de Algoritmos (0)
No hay comentarios