Práctica 3 análisis de algoritmos Rolando Carapia ESCOM
Enviado por Gino Bautista • 7 de Mayo de 2017 • Apuntes • 528 Palabras (3 Páginas) • 135 Visitas
[pic 1]
PRACTICA 3
ANALISIS DE ALGORITMOS
[pic 2][pic 3]
ANÁLISIS DE COMPLEJIDAD ALGORITMO DE FUERZA BRUTA
ANALISIS DE COMPLEJIDAD MÁXIMO SUB ARREGLO
T(1)= Θ(1) =0
Θ(n) = n
T(n) = 2T(n/2) + n
Como T(n/2) = 2T(n/4) + n/2, entonces:
T(n) = 2[2T(n/4) + n/2 ]+ n
= 4T(n/4)+n+n
= 4T(n/4)+2n
Como T(n/4) = 2T(n/8) + n/4, entonces:
T(n) = 4[2T(n/8) + n/4 ]+ n
= 8T(n/8)+n+n
= 8T(n/8)+2n
.
.
.
= 2k T(n/2k) + n + n + n+…+n [pic 4]
k veces n
= 2k T(n/2k) + kn (EC 1)
Igualando n/2k = 1:
n/2k = 1(2k) → n= 2k → k= log2(n) → k = lg (n)
Sustituyendo en EC 1:
T(n) = 2lg(n) T(n/2lg(n)) + (lg n) n
Tenemos que n/2lg(n) = n / n = 1, entonces:
T(n) = n T(1) + (lg n) n
Como T(1) = 0, entonces T(n) = n (lg n)
O(n (lg n)) <= Complejidad del algoritmo
Comparación de los 3 algoritmos
Color negro: Algoritmo fuerza bruta
Color rojo: Algoritmo máximo sub arreglo
Color azul: Algoritmo lineal
[pic 5]
Los puntos representan una prueba de 4 bytes en el arreglo
El algoritmo de fuerza bruta tardó 16 intervalos de tiempo en terminar.
El algoritmo de máximo sub arreglo tardó 4 intervalos de tiempo en terminar.
El algoritmo lineal tardó también 4 intervalos.
La ganancia de tiempo se verá a partir de 8 bytes donde la gráfica del algoritmo de fuerza bruta tiende al infinito. El comportamiento del algoritmo de máximo sub arreglo tiene un comportamiento similar.
CONCLUSIONES
El algoritmo de fuerza bruta representa un gasto computacional muy grande al momento de resolver el problema.
El algoritmo de máximo sub arreglo tiene un gasto menor al anterior, pero dependiendo de los números aleatorios en el peor caso podría llegar a tardar el mismo tiempo que el algoritmo de fuerza bruta.
Por otro lado al implementar una solución lineal, el tiempo de cómputo se ve fuertemente reducido demostrando que un problema se puede resolver de varias formas pero solo una respuesta es la más óptima.
...