4.10.2.4 Análisis Básico (3 horas) [Habilidades a,b]

Referencias Bibliográficas: [Stroustrup, 2013b] Temas
  1. Diferencias entre el mejor, el esperado y el peor caso de un algoritmo.
  2. Análisis asintótico de complejidad de cotas superior y esperada.
  3. Definición formal de la Notación Big O.
  4. Clases de complejidad como constante, logarítmica, lineal, cuadrática y exponencial.
  5. Medidas empíricas de desempeño.
  6. Compensación entre espacio y tiempo en los algoritmos.
  7. Uso de la notación Big O.
  8. Notación Little o, Big omega y Big theta.
  9. Relaciones recurrentes.
  10. Análisis de algoritmos iterativos y recursivos.
  11. Teorema Maestro y Árboles Recursivos.

Objetivos de Aprendizaje

  1. Explique a que se refiere con “mejor", “esperado" y “peor" caso de comportamiento de un algoritmo [Usage]
  2. En el contexto de a algoritmos específicos, identifique las características de data y/o otras condiciones o suposiciones que lleven a diferentes comportamientos [Usage]
  3. Determine informalmente el tiempo y el espacio de complejidad de diferentes algoritmos [Usage]
  4. Indique la definición formal de Big O [Usage]
  5. Lista y contraste de clases estándares de complejidad [Usage]
  6. Realizar estúdios empíricos para validar una hipótesis sobre runtime stemming desde un análisis matemático Ejecute algoritmos con entrada de varios tamaños y compare el desempeño [Usage]
  7. Da ejemplos que ilustran las compensaciones entre espacio y tiempo que se dan en los algoritmos [Usage]
  8. Use la notación formal de la Big O para dar límites superiores asintóticos en la complejidad de tiempo y espacio de los algoritmos [Usage]
  9. Usar la notación formal Big O para dar límites de casos esperados en el tiempo de complejidad de los algoritmos [Usage]
  10. Explicar el uso de la notación theta grande, omega grande y o pequeña para describir la cantidad de trabajo hecho por un algoritmo [Usage]
  11. Usar relaciones recurrentes para determinar el tiempo de complejidad de algoritmos recursivamente definidos [Usage]
  12. Resuelve relaciones de recurrencia básicas, por ejemplo. usando alguna forma del Teorema Maestro [Usage]

Generado por Ernesto Cuadros-Vargas , Sociedad Peruana de Computación-Peru, basado en el modelo de la Computing Curricula de IEEE-CS/ACM