5.5.5.10 Análisis Básico (4 horas)

Resultados de la carrera Outcomes: 1,6

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.

Objetivos de Aprendizaje (Learning Outcomes)

1. Explique a que se refiere con “mejor", “esperado" y “peor" caso de comportamiento de un algoritmo [Familiarizarse (Familiarity)]
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 [Evaluar (Assessment)]
3. Determine informalmente el tiempo y el espacio de complejidad de simples algoritmos [Usar (Usage)]
4. Indique la definición formal de Big O [Familiarizarse (Familiarity)]
5. Lista y contraste de clases estándares de complejidad [Familiarizarse (Familiarity)]
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 [Evaluar (Assessment)]
7. Da ejemplos que ilustran las compensaciones entre espacio y tiempo que se dan en los algoritmos [Familiarizarse (Familiarity)]
8. Usar la notación formal Big O para dar límites de casos esperados en el tiempo de complejidad de los algoritmos [Usar (Usage)]
9. 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 [Familiarizarse (Familiarity)]

Bibliografía: [Brookshear and Brylow, 2019]