Exponenciación y coeficiente binomial

PRÁCTICA 2:


EJERCICIO 1:
EXPONENCIACIÓN

EJERCICIO 2:
CALCULAR COEFICIENTE BINOMIAL-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------



EJERCICIO 1: EXPONENCIACIÓN

1. Elaborar una tabla con los tiempos medios obtenidos con los diferentesexponentes, para cada algoritmo:

n
¬T iter(n)
¬T recur(n)
128
207,63
155,63
256
155,75
155,625
512
207,5
207,625
1024
311,25
273,25
2048
259,625
195,625
4096
283,75
259,625
81921038,125
207,625
16384
986
207,625
32768
1038,125
103,75
65536
1089,875
207,625

2. 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.
Dibujar una curva para cada algoritmo, e incluir ambas en
la misma gráfica.



3. Obtener de forma teórica el orden de complejidad del algoritmoiterativo.

Podemos observar que el orden de complejidad del algoritmo iterativo es de orden lineal.



4. Consultar los apuntes e indicar el orden de complejidad del algoritmo recursivo.Conclusiones sobre la eficiencia de ambos algoritmos, especialmente el algoritmo recursivo.

Como podemos observar en las gráficas representadas, para tamaños de exponentes hasta 4000 la efectividad de amboses parecida, pero a partir de ahí el recursivo es más efectivo.

5. ¿Por qué el algoritmo recursivo es un algoritmo “Divide y Vencerás”?

Se utiliza la frase “Divide y Vencerás” para hacerreferencia a la forma de solucionar los problemas, que consiste en dividir un problema complejo en pequeños problemas de más sencillos, los cuales tendrán una solución fácil a simple vista.

EJERCICIO 2:CALCULAR COEFICIENTE BINOMIAL

1. Elaborar una tabla con los tiempos medios obtenidos para ambos algoritmos:

CoeficienteBin(2N,N)
¬T recur(ns)
¬T prog. Din(ns)
(8,4)
9654,13
5605,75
(10,5)...