Ing de sistemas

Solo disponible en BuenasTareas
  • Páginas : 5 (1245 palabras )
  • Descarga(s) : 0
  • Publicado : 8 de noviembre de 2010
Leer documento completo
Vista previa del texto
1)

double suma_aritmetica(dobule a1, double d, int n)
{
double s, an;
int i;
an = a1; O(1)
s = a1; O(1)
for (i=2; i<=n; i++)O(n)
{
an +=d; O(1)
s +=an; O(1) O(1)
}
return s; O(1)
}
T(n)=O(1)+O(1)+(O(n)*O(1))+ O(1) = O(1)+ O(1)+ O(n)+ O(1)
Max( O(1), O(1), O(n), O(1))
T(n)=O(n)

2)

public static int subsecuenciaSumaMaxima(int [] a)
{
int sumaMax = 0; O(1)int sumaActual = 0; O(1)
for (j = 0; j < a.length; j++) O(n)
{
sumaActual += a[j]; O(1)
if (sumaActual > sumaMax) O(1)
sumaMax = sumaActual; O(1)
else if (sumaActual < 0) O(1) O(1)
sumaActual = 0; O(1)
}
return sumaMax; O(1)
}


T(n)= O(1)+ O(1)+ (O(n)*O(1)) + O(1)= O(1)+ O(1)+ O(n)+ O(1)
Max( O(1), O(1), O(n), O(1) )
T(n)= O(n)

3) voidsuma_matrices(double a[][], double b[][], double c[][])
{
int i, j;
for (i=0; i<N; i++) O(n)
for(j=0; j<N; j++) O(n)
c[i][j] = a[i][j] + b[i][j]; O(1)

}
T(n)= O(n)* O(n)*O(1) = O(n2)
=max(O(n2))
T(n)= O(n2)

4)

void producto_matrices(double a[N][N], double b[N][N], double c[N][N])
{
int i, j, k;
for (i=0; i<N; i++) O(n)
for (j=0; j<N; j++) O(n)
{
c[i][j] = 0.0;O(1)
for (k=0; k<N; k++) O(n) O(n)
c[i][j] += a[i][k] + b[k][j]; O(1) O(n)
}

}
T(n)= O(n)* O(n)* O(n)= O(n3)
Max(O(n3))
T(n)= O(n3)

5)

void transponer(double m[][])
{
int i,j;
double aux;
for (i=0; i<n-1; i++) O(n)
for (j=i+1 ; j<n; j++) O(n)
{
aux = m[i][j]; O(1)
a[i][j] = m[j][i]; O(1) O(1)
m[j][i] = aux; O(1)
}
}
T(n)=O(n)* O(n)*O(1)= O(n2)
max (O(n2))
T(n)= O(n2)

6)

public static int busquedaLineal(int X, int []A)
{
int i = 0; O(1)
int n = A.length -1; O(1)
while ( (i < n) && (A[i] != X) O(n)
i++; O(1)
if (A[i] == X) O(1)
return i; O(1)
else O(1)
return -1; O(1)
}

T(n)= O(1)+ O(1)+ ( O(n)* O(1) )+ O(1)= O(1)+ O(1)+ O(n)+ O(1)
Max(O(1),O(1), O(n), O(1))
T(n)= O(n)7)

public static int busquedaBinaria(int X, int [] A)
{
int inicio = 0; O(1)
int fin = A.length – 1; O(1)
int medio;
while (inicio < = fin) O(log2 n)
{
medio = (inicio + fin) / 2; O(1)
if (A[medio] < X) O(1)
inicio = medio + 1; O(1)
else if (A[medio] > X) O(1) O(1)
fin = medio -1; O(1) O(1)
else
return medio; O(1)
}
return-1; O(1)
}

T(n)= O(1)+ O(1)+ ( O(log2 n)* O(1) )+ O(1)= O(1)+ O(1)+ O(log2 n)+ O(1)
Max(O(1), O(1), O(log2 n), O(1))
T(n) = O(log2 n)

8)

public void OrdInsercion()
{
for(int i=1; i<A.length;i++) O(n)
{
int elem = A[i]; O(1)
int j = i-1; O(1)
while (((j >= 0) && (elem <A[j])) O(n) O(n) O(n)
A[j+1] = A[j--]; O(1)
A[j+1] = elem; O(1)
}
}T(n)= O(n)* O(n)= O(n2)
Max(O(n2))
T(n)= O(n2)

9)public void OrdInsercionBin()
{
for(int i=1; i<A.length; i++) O(n)
{
int elem = A[i]; O(1)
int bajo = 0; O(1)
int alto = i-1 O(1)
while (bajo <= alto) O(log2 n)
{
int medio = (alto + bajo) /2; O(1)
if (elem < A[medio]) O(1)
alto = medio -1; O(1) O(1)
else
bajo = medio + 1; O(1)
}
for(int j=i-1; j>=bajo; j--) O(n)
A[j+1] = A[j]; O(1) O(n)
A[bajo] = elem; O(1)
}
}

T(n)= O(n)*( O(1)+ O(1)+ O(1)+ (O(log2 n)* O(1))+ (O(n)* O(1))+ O(1))
T(n)= O(n)*( O(1)+ O(1)+ O(1)+ O(log2 n)+ O(n)+ O(1))
T(n)= O(n)*(Max( O(1), O(1), O(1), O(log2 n), O(n), O(1)))
T(n)= O(n log2 n)

10)public void OrdSeleccion()
{
for(int i=0; i<A.length-1; i++) O(n)
{
int menor =i; O(1)
for (int j = i+1; j<A.length; j++) O(n)
if (A[j] < A[menor]) O(1)
menor = j; O(1)
if (menor != i) O(1)
{
aux = i; O(1)
i = menor; O(1) O(1)
menor = aux; O(1)
}
}
}

T(n)=O(n)*( O(1)+ (O(n)* (O(1)* O(1)))+ (O(1)* O(1)))
T(n)= O(n)*( O(1)+ O(n)+ O(1))
T(n)= O(n)* O(n)
=max(O(n2))
T(n)= O(n2)

11)void...
tracking img