Generalización POO
INSTITUTO POLITECNICO NACIONAL
“Escuela Superior De Cómputo”
Alumno: Mandujano Diaz Miguel Angel
Grupo: 3cm6
Profesor: Edgardo Adrián FrancoMartínez.
Unidad de Aprendizaje: Análisis de algoritmos.
Trabajo: Ejercicios complejidad algorítmica.
10 de Febrero de 2014.
Ejercicios 01: Complejidad de los algoritmos
A. Para lossiguientes 5 algoritmos determine la función de complejidad temporal y espacial.
Complejidad espacial=n+3 celdas.
Complejidad temporal=(n-1)*((n+2)).aprox n^2
Complejidad espacial=n+4 celdas.Complejidad temporal=1+((n+1)*3) aprox n
Complejidad espacial=3n+3 celdas.
Complejidad temporal=(n)*(n)*(1+(n*2)) aprox n^3
Complejidad espacial=4 celdas.
Complejidad temporal=2 + ((n-2)*4)aprox 4n
Complejidad espacial=2n+3 celdas.
Complejidad temporal= n+n aprox 2n
Para los siguientes 3 algoritmos determine las funciones de complejidad temporal y espacial, estableciendo 3casos de entrada distintospara cada algoritmo, determine de que depende el numero de operaciones para cada algoritmo, i.e. cuál es la variable a considerar en cada caso y en que afecta.N=2
Complejidad espacial=2+5 celdas.
Complejidad temporal=3+1+1 aprox n
N=3
Complejidad espacial=3+5 celdas.
Complejidad temporal=3+1+(1*2)+1 aprox n
N=4
Complejidad espacial=4+5celdas.
Complejidad temporal=3+1+(2*2)+1 aprox 2n
Es obvio que la complejidad espacial y temporal dependen de el valor de n.
N=2
Complejidad espacial=3+3=6 celdas.
Complejidadtemporal=n*(n*3)=12 aprox n^2
N=3
Complejidad espacial=3+4=7 celdas.
Complejidad temporal=3*(3*3) aprox n^2
N=4
Complejidad espacial=3+5=8 celdas.
Complejidad temporal=4*(4*3)=48 aprox n^2
Es obvio quela complejidad espacial y temporal dependen de el valor de n.
M=1 N=2
Complejidad espacial=6 celdas.
Complejidad temporal=3+1+2=6
M=2 N=4
Complejidad espacial=6 celdas.
Complejidad...
Regístrate para leer el documento completo.