Actividad04_Martinez_Nava_Jorge_Justino - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

Universidad de Guadalajara 
 
Centro Universitario de Ciencias Exactas e Ingeniería 
 
Algoritmia 
 
Profesor: Salomón Eduardo Ibarra Chávez 
 
Alumno: Jorge Justino Martinez Nava 
 
Actividad 04 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
¿Cuáles de las siguientes afirmaciones son verdaderas? Demuestre sus 
respuestas: 
a. n2 ∈ O(n3) 
Es verdadero, debido a que se tocaran en un punto, puesto que pasa por cada 
uno de los puntos, siendo este el peor caso. 
 
 
 
b. n2 ∈ Ω(n3) 
Falso, debido a que se excluyen la mayor parte de los datos que forman parte 
de n2. 
 
 
 
c. 2^n ∈ θ(2^n+1) 
Verdadero, debido a que se 
logra llegar a un punto 
intermedio, siendo el caso 
promedio. 
 
 
 
d. n! ∈ θ((n+1)!) 
Verdadero, debido a que se 
logra llegar a un punto 
intermedio, siendo el caso 
promedio. 
 
 
 
Describa qué hacen los siguientes algoritmos y determine su O-grande, 
Omega, Theta 
a. 
función T (var A:matriz) 
var i,j,filas: entero fvar 
filas=numfilas (A); 
para i=1 hasta filas-1 hacer 
para j=i+1 hasta filas hacer 
b=A[j,i]; 
A[j,i]=A[i,j]; 
A[i,j]=b; 
fpara 
fpara 
fin 
El algoritmo intercambia los valores de las filas a las columnas, creando una 
nueva matriz conocida como transpuesta. 
 
MEJOR CASO (OMEGA): 
Se evalúa en n=0 en T(n) menos en el término dominante. 
 
T(n) = 8n^2 - 4n + 4 
f(n) = n^2 
g(n) = T(n) 
T(n) = 8n^2 + 4 
c = 6 
g(n) >= 6n^2 cuando >= 0 
T(n) pertenece a omega(n^2) 
 
PEOR CASO (O-GRANDE): 
Se evalúa en n=1 en T(n) 
 
T(n) = 8^2 - 4n +4 
f(n) = n^2 
g(n) = T(n) 
T(n) = 8(1)^2 
c = 8 
g(n) < 8n^2 cuando N > 1 
T(n) pertenece a 0(n^2) 
 
 
 
 
CASO PROMEDIO (THETA): 
8n^2 - 4n + 4 representa el mejor caso y T(n) perteneciente a theta(n^2) 
representa el peor caso. 
b. 
for(i=1; i<=n; i++); 
for(j=1; j<=i;j++); 
 
sum + +; 
for(k=1; k<=n; k++); 
A[k] = k − 1; 
Funcionará recibiendo un arreglo con tamaño n que cambiará sus valores 
iniciando desde 0 e incrementando 1 en cada valor. 
 
1. n + 3 
2. n^2 - n + 3 
3. 2n + 3 
 
[ (n+3) * (2n+3) * (n2 – n + 3) ] = [ (2n2 + 9n + 9) * (n2 – n + 3) ] 
 
Polinomio: 2n^4 + 7n^3 + 6n^2 + 18n + 27 
 
 
 
 
 
 
MEJOR CASO (OMEGA): 
Se evalúa en n=0 en T(n) menos 
en el término dominante. 
 
T(n) = 2n^4 + 7n^3 + 6n^2 + 18n 
+ 27 
f(n) = n^4 
g(n) = T(n) 
T(n) = 2n^4 
c = 2 
g(n) >= 2n^4 cuando N >= 0 
T(n) pertenece a omega(n^4) 
 
PEOR CASO (O-GRANDE): 
Se evalúa en n=1 en T(n) 
 
 
 
 
 
 
CASO PROMEDIO (THETA): 
 
2n^4 + 7n^3 + 6n^2 + 18n + 27 representa el mejor caso y 
T(n) pertenece a O(n^4) representa el peor caso. 
 
 
 
c. 
for (int i= 0; i < N; i++) { 
c= i; 
while (c > 1) { 
algo_de_O(1) 
c= c/2; 
}}