Practicas de Algoritmia para la casa

[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

Ejercicio 1.

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

1. 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]

1. Obtener de forma teórica el orden de complejidad del algoritmo iterativo.

[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.

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

[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).

...