Upload
victor
View
227
Download
0
Embed Size (px)
Citation preview
7/23/2019 Estructuras de Datos UGR
1/33
Modulo I
Introduccin al anlisis de laeficiencia de Algoritmos
7/23/2019 Estructuras de Datos UGR
2/33
Objetivos
Concepto de efciencia
Concepto de operacin elemental
Notaciones asintticas Saber calcular la efciencia de un
algoritmo
7/23/2019 Estructuras de Datos UGR
3/33
Comparacin de algoritmos
Es frecuente disponer de ms de un posible algoritmopara resolver un problema dado:
Con cul nos quedamos?
Estudio del uso de los recursos:
tiempo
espacio El uso de los recursos se distribuye en:
diseo implementacin
explotacin
7/23/2019 Estructuras de Datos UGR
4/33
Factores en el uso de recursos
Principio de Invarianza:dos implementaciones de unmismo algoritmo no diferirn ms ue en una constantemultiplicativa!
Si y son los tiempos de dos implementacionesde un mismo algoritmo, se verifica:
7/23/2019 Estructuras de Datos UGR
5/33
"rdenacin por InsercinAlgoritmo fuer#a bruta:
$no a uno% y desde el segundo elemento% despla#a de i#uierda a derec&a%&asta encontrar la posicin correcta
'( void insercion)vector*int+ , array-
'. /
'0 int i% 1% valor2
'3 for )i 4 (2 i * array!si#e)-2 55i-
'6 / valor 4 array7i82
'9 for )1 4 i2 1 + ' ,, array71 (8 + valor2 1-'; array718 4 array71 (82
'< array718 4 valor2
(( =
(. =
>?e u@ operacin depender eltiempo de e1ecucin
7/23/2019 Estructuras de Datos UGR
6/33
"rdenacin por Insercin
Algoritmo fuer#a bruta:
$no a uno% y desde el segundo elemento% despla#a de i#uierda a derec&a%&asta encontrar la posicin correcta
'( void insercion)vector*int+ , array-'. /
'0 int i% 1% valor2
'3 for )i 4 (2 i * array!si#e)-2 55i-
'6 / valor 4 array7i82
'9 for )1 4 i2 1 + ' ,, array71 (8 + valor2 1-
'; array718 4 array71 (82
'< array718 4 valor2
(( =
(. =
>Cuntas veces se e1ecuta la comparacin
Entradas: B nmeros aleatorios!
B Comparaciones
Tiempo
5.000 6.2 Millones 0.13
10.000 25 Millones 0.43
20.000 99 Millones 1.50
40.000 400 Millones 5.6
80.000 1.600 Millones 23 seg
7/23/2019 Estructuras de Datos UGR
7/33
"rdenacin por Insercin>Cuntas veces se e1ecuta la comparacin
B Comparaciones Tiempo
5.000 6.2 Millones 0.13
10.000 25 Millones 0.43
20.000 99 Millones 1.50
40.000 400 Millones 5.6
80.000 1.600 Millones 23 seg
El nmero de comparaciones crece de formaCuadrtica )BD-
El tiempo necesario crece de forma cuadrticaCon el nmero de entradas )(!G('H);- BD -
5 10 20 40 80
0
5
10
15
20
25
N
Tiempo
0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.50
200
400
600
800
1000
1200
1400
1600
1800
N
Comp
7/23/2019 Estructuras de Datos UGR
8/33
Eficiencia
Eficiencia:medida del uso de los recursos en funcin del tamaode las entradas
T(n): iempo empleado para una entrada de tamao n
Es necesario un anlisis asinttico
Ja eleccin de una buena estructura de datos es fundamentalpara crear un buen algoritmo
7/23/2019 Estructuras de Datos UGR
9/33
Krdenes de eficiencia)I-
Orden de Eficiencia:$n algoritmo tiene un tiempo de eecuci!nde orden f(n)% para una funcin dada f% si existe una constantepositiva cy una implementacin del algoritmo capa# deresolver cada caso del problema en un tiempo acotadosuperiormente por cf(n)% donde nes el tamao del problemaconsiderado!
Krdenes ms &abituales:
lineal:
cuadrtico: " polinmico: % con #
logarLtmico:
exponencial: , c $ %
7/23/2019 Estructuras de Datos UGR
10/33
Krdenes de eficiencia)II-
Comparacin grfica de algunos rdenes de eficiencia
7/23/2019 Estructuras de Datos UGR
11/33
Medidas de la eficiencia
Enfoue prctico )a posteriori-
Enfoue terico )a priori-
Enfoue &Lbrido
ituaciones: Neor caso
Caso promedio
Me1or caso
Anlisis amorti#ado
7/23/2019 Estructuras de Datos UGR
12/33
"peracin elemental
Definicin: "peracin de un algoritmo cuyo tiempo de e1ecucinse puede acotar superiormente por una constante!
Nara nuestro anlisis slo contar el nmero de operacioneselementales e1ecutadas y no el tiempo exacto necesario paracada una de ellas!
7/23/2019 Estructuras de Datos UGR
13/33
"peracin elemental: Consideraciones
(! JLnea de cdigo 4 un nmero variable de operaciones elementales!N!e!: sea&un vector con nelementos y
el tiempo para calcular x depende de n% no es constante!
.! Algunas operaciones matemticas no son operaciones elementales!N!e!: sumas y productos dependen de la longitud de los operandos!in embargo% en la prctica se consideran elementales siempre uelos datos ue se usen tengan un tamao ra#onable!En la prctica% consideraremos las operaciones suma% diferencia%multiplicacin% divisin% mdulo% operaciones booleanas%
comparativas y asignaciones como elementales% )salvo ue seindiue otra cosa-!
7/23/2019 Estructuras de Datos UGR
14/33
Oeglas de clculo del tiempo dee1ecucin
entencias simples Ploues de sentencias Pucles entencias condicionales Jlamadas a funciones
7/23/2019 Estructuras de Datos UGR
15/33
entencias simples
Consideraremos ue cualuier sentencia simple )lectura% escritura%asignacin%!!!- va a consumir un tiempo constante% % salvo ue lasentencia contenga una llamada a funcin!
1: for (i = 0; i < n-1; i++) {
2: indice = i;3: for (j = i+1; j < n; j++) {
4: if (A[j] < A[indice])
5: indice = j;
6: temor!" = A[indice];
#: A[indice] = A[i];$: A[i] = temor!";
%: &;
10: &
7/23/2019 Estructuras de Datos UGR
16/33
entencias simples
Consideraremos ue cualuier sentencia simple )lectura% escritura%asignacin%!!!- va a consumir un tiempo constante% % salvo ue lasentencia contenga una llamada a funcin!
1: i = 0;
2: indice = i;
3: j = i+1; j++
4: A[j] < A[indice]
5: temor!" = A[indice];
7/23/2019 Estructuras de Datos UGR
17/33
Ploues de sentencias
e aplica la regla de la suma% de forma ue secalcula el tiempo de e1ecucin tomando el mximode los tiempos de e1ecucin de cada una de laspartes )sentencias individuales% bucles o
condicionales- en ue puede dividirse!
7/23/2019 Estructuras de Datos UGR
18/33
Pucles
iempo para un bucle:
la suma del tiempo invertido en cada iteracin!
?eberLa incluir: el tiempo propio del cuerpo y el asociado a la evaluacinde la condicin y su actuali#acin% en su caso! i se trata de unacondicin sencilla )sin llamadas a funcin- el tiempo es !
Cuando se trata de un bucle donde todas las iteraciones son iguales%entonces el tiempo total ser el producto del nmero de iteracionespor el tiempo ue reuiere cada una!
7/23/2019 Estructuras de Datos UGR
19/33
Pucles
Ejemplo 1:1: for (i = 0; i < n; i++)2: for (j = 0; j < n; j++)
3: A[i][j] = 0;
Ejemplo 1:1: for (i = 0; i < n; i++)2: for (j = 0; j < n; j++)
3: A[i][j] = 0;
7/23/2019 Estructuras de Datos UGR
20/33
Pucles
Ejemplo 1:1: for (i = 0; i < n; i++)
2: for (j = 0; j < n; j++)3: A[i][j] = 0;
7/23/2019 Estructuras de Datos UGR
21/33
Pucles
Ejemplo 2:1: ' = 0;
2: i"e (' < n ** A['] = ,)
3: '++;
7/23/2019 Estructuras de Datos UGR
22/33
entencias condicionales
El tiempo de ejecucin es el mximo tiempo de la parte if dela parte else! de "orma #ue si son! respectivamente! ser %
Ejemplo:
1: if (A[0][0] == 0)
2: for (i = 0; i < n; i++)
3: for (j = 0; j < n; j++)
4: A[i][j] = 0;
5: e"e
6: for (' =0; ' < n; '++)
#: A[']['] = 1;
7/23/2019 Estructuras de Datos UGR
23/33
Frmulas tiles
7/23/2019 Estructuras de Datos UGR
24/33
Jlamadas a funciones)I-
i una determinada funcin N tiene una eficiencia decon la medida del tamao de los argumentos% cualuierfuncin o procedimiento ue llame a N tiene en la llamadauna cota superior de eficiencia de !
Jas asignaciones con diversas llamadas a funcin debensumar las cotas del tiempo de e1ecucin de cada llamada!
Ja misma consideracin es vlida para las condiciones debucles y condicionales!
7/23/2019 Estructuras de Datos UGR
25/33
E1emplo: Notenciacin
1: .oid ejem"o1 (int n) {
2: int / cont!dor;
3: cont!dor = 0;
4: / = 2;
5: i"e (/
7/23/2019 Estructuras de Datos UGR
26/33
E1emplo: Insercin)I-
1: .oid inercion(int A[] int n) {
2: int i j .!"or;
3: for (i = 1; i < n; i++) {
4: .!"or = A[i];
5: j = i;
6: i"e ((j 0) ** (A[j-1] .!"or)) {
#: A[j] = A[j-1];
$: j--;
%: &
10: A[j] = .!"or;
11: &
12: &
7/23/2019 Estructuras de Datos UGR
27/33
E1emplo: Insercin)II-
7/23/2019 Estructuras de Datos UGR
28/33
E1emplo: eleccin)I-
1: .oid e"eccion(int A[] int n) {
2: int i j min t;
3: for (i = 0; i < n - 1; i++) {
4: min = i;
5: for (j = i + 1; j < n; j++)
6: if (A[j] < A[min])
#: min = j;
$: t = A[min];
%: A[min] = A[i];
10: A[i] = t;
11: &
12: &
7/23/2019 Estructuras de Datos UGR
29/33
E1emplo: eleccin)II-
7/23/2019 Estructuras de Datos UGR
30/33
E1emplo)I-
1: .oid ejem"o2(int n) {
2: int i j ';
3: for (i = 1; i < n; i++)
4: for (j = i+1; j < n + 1; j++)
5: for (' = 1; ' < j + 1; '++)
6: A"n! entenci! (1)
#: &
&'neas -.*: veces
&'neas ).*:
E1 l
7/23/2019 Estructuras de Datos UGR
31/33
E1emplo)II-
&'neas -./:
E1 l
7/23/2019 Estructuras de Datos UGR
32/33
E1emplo)II-
&'neas -./:
"t 1 l
7/23/2019 Estructuras de Datos UGR
33/33
"tro e1emplo
1: .oid ejem"o3(int n) {
2: int i j / 7;
3: for (i = 1; i < n+1; i++)
4: if (i 8 2 == 0) {
5: for (j = i; j < n+1; j++)6: /++;
#: for (j = 1; j < i+1; j++)
$: 7++;
%: &
10: &