SandovalPadillaReporteActividad 3 - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

UNIVERSIDAD DE GUADALAJARA
Centro Universitario de Ciencias Exactas e Ingenierías
Algoritmia
Actividad 3: Tiempo polinomial 
Alumno: Sandoval Padilla Fernando Cesar
Docente: Ibarra Chávez Salomón Eduardo
Código: 215685409
Sección: D02
	
19 de Febrero de 2020
1. Escriba la función que define el tiempo de ejecución T(n) para el mejor y peor caso del siguiente algoritmo. Escribe el procedimiento para llegar a la respuesta. 
//Entrada A[0 ... n - 1] 
desde i=0 hasta n – 2 hacer 
desde j=i + 1 hasta n -1 hacer 
si A[i] = A[j] regresar falso; 
de lo contrario 
regresar verdadero 
finsi 
Resultado: 
1+1+[3(n-2)*3(n-1)+3]2+[3(n-2)*3(n-1)+3]2+3(n-2)[3(n-1)+3]2+9(n²-2)+9(n-2)
O(n²)
Ω(2+9(n²-2)+9(n-2))
2. Escriba la función que define el tiempo de ejecución T(n) para el mejor y peor caso del siguiente algoritmo. Escribe el procedimiento para llegar a la respuesta. 
//Entrada T[1 ... n] 
desde i=1 hasta n – 1 hacer 
minj=i; minx=T[i] 
desde j=i + 1 hasta n hacer 
si T[j] < minx 
minj=j; 
de lo contrario minx=T[j]; 
finsi 
T[minj]=T[i]; T[i]=minx; 
Resultado: 
T(Ω)=1+[3+2(n-1)(1+(3+4)n)2+[5(n-1)7n]2+35(n²-n)
T(O)= 1+[3+2(n-1)(1+(3+4)n)2+[5(n-1)7n]2+35(n²-n)
3. Dos algoritmos requieren n² días y n³ segundos respectivamente para resolver casos de tamaño n ¿Cuál es el tamaño del caso más pequeño en el cual el primer algoritmo es más rápido que el segundo? ¿Aproximadamente, cuánto tiempo tarda en resolver este caso? Hacer la gráfica correspondiente al caso. 
Resultado:
N² es más rápida cuando N es<72000
ALGORITMOS N² Y N³