Practicas de Algoritmia para la casa
Guillermo CantonInforme5 de Noviembre de 2015
1.011 Palabras (5 Páginas)115 Visitas
[pic 1][pic 2]
Curso 2012-2013
Recurrencia.
Guillermo Cantón Tortosa.
Grupo 1º A.
LÓGICA Y ALGORÍTMICA
1º grado en ingeniería informática
[pic 3] | Universidad de Almería |
Ejercicio 1.
- Elaborar una tabla con los tiempos medios obtenidos con los diferentes exponentes, para cada algoritmo:
n | Titer(n) nanosegundos | Trecur(n) nanosegundos |
512 | 4724 | 4666 |
1024 | 8165 | 5249 |
2048 | 15223 | 5949 |
4096 | 29338 | 6415 |
8192 | 57510 | 6999 |
16384 | 125344 | 7932 |
32768 | 228524 | 8282 |
- A partir de esta tabla obtener una gráfica en la que representamos los tiempos de los dos algoritmos: tiempo de ejecución vs tamaño del exponente.
[pic 4]
- Obtener de forma teórica el orden de complejidad del algoritmo iterativo.
n | log(n) | Titer(n) nanosegundos | Trecur(n) nanosegundos | Titer(n) log | Trecur(n) log |
512 | 9 | 4724 | 4666 | 12,20579325 | 12,18797059 |
1024 | 10 | 8165 | 5249 | 12,99523717 | 12,35782688 |
2048 | 11 | 15223 | 5949 | 13,89396508 | 12,53843146 |
4096 | 12 | 29338 | 6415 | 14,8404829 | 12,64723355 |
8192 | 13 | 57510 | 6999 | 15,81152522 | 12,77293309 |
16384 | 14 | 125344 | 7932 | 16,93553341 | 12,95346896 |
32768 | 15 | 228524 | 8282 | 17,80198616 | 13,01576349 |
[pic 5]
Calculo:
Base ← base
exponente ← exponente
ExponenteFuerzabruta()
solucion←1
for i← 0 hasta i=exponente-1
solución ← solución *base
devuelve solución
Línea 1: dos asignaciones: tiempo constante.
Bucle:
- Dentro del bucle se realiza una operación aritmética lo q es igual a una constante.
- Como el bucle se repite el valor de la variable exponente entonces:
TBucle <= = C*Exponente[pic 6]
Tiempo del algoritmo: Titer = ϴ(Exponente)
Esto quiere decir que el algoritmo es de tipo ϴ(n) como se puede observar en la gráfica la pendiente de la recta también es próxima a 1.
De esta manera comprobamos que el crecimiento del algoritmo es de crecimiento de tipo n.
- Consultar los apuntes e indicar el orden de complejidad del algoritmo recursivo. Conclusiones sobre la eficiencia de ambos algoritmos, especialmente el algoritmo recursivo.
n | log(n) | Titer(n) nanosegundos | Trecur(n) nanosegundos | Titer(n) log | Trecur(n) log |
512 | 9 | 4724 | 4666 | 12,20579325 | 12,18797059 |
1024 | 10 | 8165 | 5249 | 12,99523717 | 12,35782688 |
2048 | 11 | 15223 | 5949 | 13,89396508 | 12,53843146 |
4096 | 12 | 29338 | 6415 | 14,8404829 | 12,64723355 |
8192 | 13 | 57510 | 6999 | 15,81152522 | 12,77293309 |
16384 | 14 | 125344 | 7932 | 16,93553341 | 12,95346896 |
32768 | 15 | 228524 | 8282 | 17,80198616 | 13,01576349 |
[pic 7]
En este algoritmo se ve en la gráfica que la pendiente se aproxima a 0 con lo que deducimos que es un algoritmo más rápido q el de tipo (n) así q podemos suponer es de tipo log(n).
También vemos q es de tipo log(n) por que el problemas se resuelve transformándolo en una serie de problemas más pequeños, dividendo el tamaño de problema por una fracción constante el cada paso, en este caso dividiendo el exponente por 2.
La conclusión es que para tamaños de exponentes hasta 4000, la rapidez de ambos algoritmos es parecida, pero para exponentes mayores el recursivo es muchísimo más efectivo.
- ¿Por qué el algoritmo recursivo es un algoritmo “Divide y Vencerás”?
Esta frase se utiliza por que divide el problema complejo en pequeños problemas más simples. De esta forma se agiliza el cálculo de las operaciones.
...