PDF de programación - Tiempo de Ejecución - Análisis y Diseño de Algoritmos

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