-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathinforme.txt
108 lines (79 loc) · 4.62 KB
/
informe.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
ALGORITMOS - PRÁCTICA 1
Pablo Portas Lopez
Pablo Míguez Muíño
Maite Liu González Vázquez
1) Contexto
En esta práctica implementamos 3 algoritmos que calculan la sucesión de
Fibonacci y, tras comprobar que los tres funcionan correctamente,
medimos sus tiempos de ejecución para unos valores de n dados.
Con esto tratamos de realizar una comprobación empírica de las complejidades
teóricas de los tres algoritmos.
2) Datos de la máquina
Modelo de hardware: HP Victus by HP Gaming Laptop 15-fa0xxx
Memoria: 16.0 GiB
Procesador: 12th Gen Intel® Core™ i5-12500H × 16
Nombre del SO: Ubuntu 22.04.5 LTS
Versión del Kernel: 6.8.0-45-generic
Tipo de SO: 64 bits
Unidad de tiempo utilizada: microsegundos
3) Comprobación de los algoritmos
n fib1 fib2 fib3
---------------------------
2 1 1 1
4 3 3 3
8 21 21 21
16 987 987 987
32 2178309 2178309 2178309
---------------------------
4) Tablas de tiempos:
1. Presentación de resultados del Algoritmo 1
función n tiempo t/1.1**n t/n t/n**2
--------------------------------------------------------------------------------
(*) fib1 2 0.01050 0.008678 0.004011 0.00262500
(*) fib1 4 0.03450 0.023564 0.005033 0.00215625
(*) fib1 8 0.24150 0.112662 0.005141 0.00094336
(*) fib1 16 10.26290 2.233506 0.004650 0.00015660
fib1 32 14079.00000 666.815803 0.002890 0.00000328 #
--------------------------------------------------------------------------------
cota subestimada cota ajustada cota sobreestimada
cte = 0.0047087
(*) tiempo promedio en respectivos k = 10000 ejecuciones del algoritmo
1.1 Observaciones
En n = 32 podemos observar un salto desproporcionado del tiempo, ya que pasamos de 10.263 a 14079.000,
por lo que consideramos esta medición anómala. (#)
A excepción del dato anómalo podemos afirmar una complejidad lineal. Rondando la constante que indicamos.
2. Presentación de resultados del Algoritmo 2
función n tiempo t/n**0.8 t/n t/(n*log(n))
--------------------------------------------------------------------------------
(*) fib2 1000 1.38700 0.005522 0.001387 0.00020079
(*) fib2 10000 14.90780 0.009406 0.001491 0.00016186
(*) fib2 100000 166.89960 0.016690 0.001669 0.00014497
fib2 1000000 1689.00000 0.026769 0.001689 0.00012225
fib2 10000000 15028.00000 0.037749 0.001503 0.00009324
--------------------------------------------------------------------------------
cota subestimada cota ajustada cota sobreestimada
cte = 0.0015478
(*) tiempo promedio en respectivos k = 10000 ejecuciones del algoritmo
2.1 Observaciones
Al contario que en el algoritmo 1 vemos una mayor continuidad en los datos que nos devuelve
el algoritmo 2. Sin detectar ningún dato anómalo.
Al principio podemos ver que la cota ajustada aumenta, pero se estabiliza cuando n crece,
cercano a la constante que indicamos.
3. Presentación de resultados del Algoritmo 3
función n tiempo t/sqrt(log(n)) t/log(n) t/n**0.5
--------------------------------------------------------------------------------
(*) fib3 1000 0.02930 0.011148 0.004242 0.00092655
(*) fib3 10000 0.03770 0.012422 0.004093 0.00037700
(*) fib3 100000 0.04700 0.013852 0.004082 0.00014863
(*) fib3 1000000 0.06040 0.016250 0.004372 0.00006040
(*) fib3 10000000 0.07030 0.017510 0.004362 0.00002223
--------------------------------------------------------------------------------
cota subestimada cota ajustada cota sobreestimada
cte = 0.0042302
(*) tiempo promedio en respectivos k = 10000 ejecuciones del algoritmo
3.1 Observaciones
El crecimiento de tiempo de este algoritmo es mucho más predecible. Tiene un crecimiento logarítmico y
todos los datos respaldan esta tendencia. Con una constante clara, que hemos indicado.
5) Conclusión
El algoritmo fib3 es claramente superior a los otros dos algoritmos. Con una velocidad sin comparación y una
escalabilidad predecible.