-
Notifications
You must be signed in to change notification settings - Fork 0
/
InformePracticaFinal.txt
140 lines (80 loc) · 6.59 KB
/
InformePracticaFinal.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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
Práctica Final de algoritmos. AuxOrd
A 18 de enero de 2024
Autores de la práctica:
- Levi Barros García
- Introducción: En esta práctica vamos a implementar el algoritmo auxOrd a partir del pseudocódigo dado, convirtiéndolo a código C realizando su respectiva implementación. Nos apoyaremos en prácticas anteriores para realizar las mediciones en tres casos, vector aleatorio, ascendente y descendente. Obtendremos su cálculo de la complejidad a partir de unas mediciones y cáclulos implementados en el código. Además se ha implementado una función test para verficiar el correcto funcionamineto del algoritmo en cuestión a la ordenación de los vectores pertinentes.
- Máquina de medición:
- Sistema Operativo: Linux 5.15.0-84-generic
- Procesador: Intel(r) Core(tm) i5-8300H CPU @ 2.30GHz × 8
- Memoria Ram: 8 GB DDR4
- Tarjeta Gráfica: NVIDIA Corporation GP107M [GeForce GTX 1050 Mobile]
- Arquitectura Hardware: x86_64
- Kernel: #93~20.04.1-Ubuntu SMP
Tabla de tiempos en microsegundos obtenida con vectores aleatorios :
Índice:
- n: el tamaño de los vectores
- t(n): son los tiempos
- n ^ 0.8: es la cota subestimada
- n ^ 1.1: es la cota ajustada
- n ^ 1.2: es la cota sobrestimada
- *: Indica que el tiempo de ejecución del vector fue menor que 500 ms y se hizo la media de los tiempos de ese vector ejecutado 100 veces.
- #: Mediciones anómalas
Ordenacion Aleatorio
n t(n) t(n) / n^0.8 t(n) / n^1.1 t(n) / n^1.2
(*) 500 61.910 0.42912597 0.06651105 0.03572702
(*) 1000 134.440 0.53521528 0.06737961 0.03376980
(*) 2000 291.410 0.66631633 0.06813519 0.03186166
4000 625.000 0.82078994 0.06817325 0.02974459
8000 1321.000 0.99639337 0.06722082 0.02736496
16000 2825.000 1.22383386 0.06706354 0.02547267
32000 5967.000 1.48469093 0.06608320 0.02341942
64000 12604.000 1.80121027 0.06511940 0.02153240
cte = 0.067
Discusión: Se han detectado tres mediciones de menos de 500ms para los vectores de tamaño 500, 1000, 2000. La cte es sobre 0.067, y se aproxima a una O(n^1.1). No se han detectado anomalías en las mediciones.
Para acabar también hemos observado que en la cota subestimada los valores de esta van siguiendo un crecimiento constante ya que en todo momento la cota tiende siempre a crecer, y con respecto a la cota sobrestimada hemos observado que va tendiendo a cero a medida que se va acercando al infinito por lo tanto va decreciendo progresivamente.
Tabla de tiempos en microsegundos obtenida para aleatorios ascendentes :
Índice:
- n: el tamaño de los vectores
- t(n): son los tiempos
- n ^ 1.8: es la cota subestimada
- n^1.985: es la cota ajustada
- n ^ 2.2: es la cota sobrestimada
- *: Indica que el tiempo de ejecución del vector fue menor que 500 ms y se hizo la media de los tiempos de ese vector ejecutado 100 veces.
- #: Mediciones anómalas
Ordenacion Ascendente
n t(n) t(n) / n^1.8 t(n) / n^1.985 t(n) / n^2.2
(*) 500 189.060 0.00262092 0.00083013 0.00021821
1000 731.000 0.00291016 0.00081081 0.00018362
2000 2877.000 0.00328917 0.00080611 0.00015728
4000 11417.000 0.00374838 0.00080810 0.00013584
8000 45574.000 0.00429690 0.00081486 0.00011801
16000 181911.000 0.00492542 0.00082164 0.00010252
32000 727379.000 0.00565576 0.00082992 0.00008921
64000 2909053.000 0.00649573 0.00083846 0.00007765
cte = 0.00082
Discusión: Se han detectado tres mediciones de menos de 500ms para el vector de tamaño 500. La cte es sobre 0.00082, y se aproxima a una O(n^1.1). No se han detectado anomalías en las mediciones.
Para acabar también hemos observado que en la cota subestimada los valores de esta van siguiendo un crecimiento constante ya que en todo momento la cota tiende siempre a crecer, y con respecto a la cota sobrestimada hemos observado que va tendiendo a cero a medida que se va acercando al infinito por lo tanto va decreciendo progresivamente.
Tabla de tiempos en microsegundos obtenida para vectores aleatorios descendentes :
Índice:
- n: el tamaño de los vectores
- t(n): son los tiempos
- n ^ 1.8: es la cota subestimada
- n²: es la cota ajustada
- n ^ 2.2: es la cota sobrestimada
- *: Indica que el tiempo de ejecución del vector fue menor que 500 ms y se hizo la media de los tiempos de ese vector ejecutado 100 veces.
- #: Mediciones anómalas
Ordenacion Descendente
n t(n) t(n) / n^1.8 t(n) / n^2 t(n) / n^2.2
(*) 500 411.240 0.00570098 0.00164496 0.00047464
1000 1609.000 0.00640554 0.00160900 0.00040416
2000 6354.000 0.00726429 0.00158850 0.00034736
4000 25328.000 0.00831559 0.00158300 0.00030135
8000 101310.000 0.00955191 0.00158297 0.00026233
16000 405043.000 0.01096693 0.00158220 0.00022826
32000 1620586.000 0.01260092 0.00158260 0.00019877
64000 6471597.000 0.01445065 0.00157998 0.00017275
cte = 0.00158
Discusión: Se han detectado tres mediciones de menos de 500ms para el vector de tamaño 500. La cte es sobre 0.00158, y se aproxima a una O(n^2). No se han detectado anomalías en las mediciones.
Para acabar también hemos observado que en la cota subestimada los valores de esta van siguiendo un crecimiento constante ya que en todo momento la cota tiende siempre a crecer, y con respecto a la cota sobrestimada hemos observado que va tendiendo a cero a medida que se va acercando al infinito por lo tanto va decreciendo progresivamente.
Conclusión: Tras comprobar los tres casos de inicialización de vectores para el algoritmo auxOrd, se ha concluído que este algoritmo resulta bastante eficiente para vectores de incialización aleatoria llegand a conseguir una O(n^1.1) aproximadamente. Sin embargo para vectores con inicialización ascendente y descendente podemos observar que el algoritmo no es tan eficiente para estos casos, concluyendo que su complejidad se aproxima a O(n^2).
Cabe destacar que para la obtención de estos tiempos se ha ejecutado el algoritmo un número considerable de veces para la obtención de tiempos estables y ajustados la depuración de errores y para evitar anomalías en las mediciones.