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