Complajidad ASIGNATURA: ESTRUCTURA DE DATOS

[pic 2]

PRÁCTICA DE LABORATORIO

CARRERA: COMPUTACION

ASIGNATURA: ESTRUCTURA DE DATOS

NRO. PRÁCTICA:

1

TÍTULO PRÁCTICA: ANALISIS DE ALGORITMOS

OBJETIVO

Identificar la complejidad de algoritmos a través del sistema de notación O mayúscula.

INSTRUCCIONES 

1. Implementar el algoritmo de búsqueda secuencial en un arreglo.

1. Obtener el tiempo de ejecución para N= 10.000, 20.000, 40.000, 80.000, 160.000, 320.000 y 640.000.
2. Graficar la curva de crecimiento del tiempo de ejecución obtenido.
3. Analizar y comprobar la complejidad del algoritmo a través de T(N)/F(N) con complejidad lineal, logarítmica, cuadrática y cúbica.
4. ¿Cuál es la complejidad del algoritmo? Justificar su respuesta

1. Implementar el algoritmo para obtener la factorial de un número.

1. Obtener el tiempo de ejecución para N = 1, 2, 4, 8, 16, 32, 64.
2. Graficar la curva de crecimiento del tiempo de ejecución obtenido.
3. Analizar y comprobar la complejidad del algoritmo a través de T(N)/F(N) con complejidad lineal, logarítmica, cuadrática y cúbica.
4. ¿Cuál es la complejidad del algoritmo? Justificar su respuesta

1. Puntos más próximos

1. Obtener el tiempo de ejecución para N= 10, 100, 1.000, 10.000, 100.000 y 1.000.000
2. Graficar la curva de crecimiento del tiempo de ejecución obtenido.
3. Comprobar la complejidad del algoritmo al analizar los tiempos de ejecución obtenidos, teniendo un factor de 10. Además, calcular el tiempo de ejecución para 10.000.000 y 100.000.000 elementos
4. ¿Cuál es la complejidad del algoritmo? Justificar su respuesta

1. Suma máxima contigua (cúbica, cuadrática y lineal)

1. Obtener el tiempo de ejecución para N= 5, 25, 125, 625, 3.125, 15.625, y 78.125
2. Graficar la curva de crecimiento de los tiempos de ejecución obtenidos.
3. Comprobar la complejidad del algoritmo al analizar los tiempos de ejecución obtenidos, teniendo un factor de 5. Además, calcular el tiempo de ejecución para 390.625 y 1.953.125 elementos
4. Analizar y comprobar la complejidad del algoritmo a través de T(N)/F(N) con complejidad lineal, logarítmica, cuadrática y cúbica
5. ¿Cuál es la complejidad del algoritmo? Justificar su respuesta

1. Un elemento mayoritario en una matriz A de tamaño N (filas por columnas) es un elemento que aparece más de N/2 veces (siempre habrá un elemento mayoritario en cada matriz). Por ejemplo:

        3, 3, 4, 2, 4, 4, 2, 4, 4 (el elemento mayoritario = 4)

        3, 3, 4, 2, 4, 4, 2, 4 (no tiene elemento mayoritario)

Escriba un algoritmo para determinar el elemento mayoritario, si es que existe uno, o para informar que no existe tal elemento.

1. Obtener el tiempo de ejecución para N = 10, 100, 1.000, 10.000, 100.000 y 1.000.000
2. Graficar la curva de crecimiento de los tiempos de ejecución obtenidos.
3. Comprobar la complejidad del algoritmo al analizar los tiempos de ejecución obtenidos, teniendo un factor de 5. Además, calcular el tiempo de ejecución para 390.625 y 1.953.125 elementos
4. Analizar y comprobar la complejidad del algoritmo a través de T(N)/F(N) con complejidad lineal, logarítmica, cuadrática y cúbica
5. ¿Cuál es la complejidad del algoritmo? Justificar su respuesta

1. Para cada uno de los siguientes fragmentos de programa, haga lo siguiente:

1. Proporcione un análisis O mayúscula.
2. Implemente el código y ejecútelo para N = 10, 100, 1.000, 10.000, 100.000 y 1.000.000
3. Compruebe su análisis con los tiempos de ejecución reales, ya sea analizando el tiempo de ejecución ó a través de T(N)/F(N).
4. ¿Cuál es la complejidad del algoritmo? Justificar su respuesta

// Fragmento 1

for( int i = 0; i < n; i++ )

   sum++;

// Fragmento 2

for( int i =0; i < n; i += 2 )

   sum++;

// Fragmento 3

for( int i = 0; i < n; i++ )

   for( int j =0; j < n; j++)

      sum++;

// Fragmento 4

for( int i = 0; i < n; i++ )

   sum++;

for( int j = 0; j < n; j++)

   sum++;

// Fragmento 5

for(int i = 0; i < n; i++)

   for(int j = 0; j < n*n; j++)

      sum++;

// Fragmento 6

for( int i = 0; i

   for( int j = 0; j

       sum++;

// Fragmento 7

for( int i =0; i

   for( int j = 0; j < n * n; j++ )

      for( int k = 0; k< j; k++ )

         sum++:

// Fragmento 8

for( int i = 1; i < n; i = i * 2 )

   sum++;

ACTIVIDADES POR DESARROLLAR 

1. Implementar los algoritmos en el lenguaje de programación de Java

2. Obtener los tiempos de ejecución para varios tamaños de N.

3. Analizar la complejidad del algoritmo

4. Graficar las curvas de crecimiento

4. Comprobar la complejidad del algoritmo

5. Generar informe de resultados (incluye implementación, análisis del algoritmo, curvas de crecimiento, tablas de comprobación, etc)

RESULTADO(S) OBTENIDO(S):

• Al finalizar la práctica los estudiantes podrán analizar e identificar la complejidad de algoritmos basado en la notación O mayúscula.

CONCLUSIONES:

• Los estudiantes podrán utilizar sistemas de notación para identificar la complejidad de algoritmos.

RECOMENDACIONES:

• Aplicar buenas prácticas de programación
• Programar según las convenciones de los códigos de Java.