5.20.4.5 Marco de Análisis de Complejidad (3 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Sipser, 2012,Cormen et al., 2022]

Temas

1. Marco de Análisis de Complejidad:
   1. Rendimiento de un algoritmo en el mejor caso, caso promedio y peor caso
   2. Mediciones empíricas y relativas (Orden de Crecimiento)
   3. Tamaño de entrada y operaciones primitivas
   4. Eficiencia de tiempo y espacio
2. Mediciones empíricas de rendimiento
3. Compromisos tiempo-espacio en algoritmos

Aprendizaje esperado (Learning Outcomes)

1. Preparar una presentación que explique a estudiantes de primer año los conceptos básicos de complejidad algorítmica incluyendo comportamiento de algoritmo en mejor caso, caso promedio y peor caso, notaciones Big-O, Omega y Theta, clases de complejidad, compromisos tiempo-espacio, medición empírica e impacto en problemas prácticos [Explicar]
2. Para cada algoritmo en la unidad Fundamentos Algorítmicos (AL) -FoundationalDataStructuresAlgorithms, explicar su clase de complejidad de tiempo de ejecución y por qué pertenece a esta clase [Explicar]
3. Evaluar informalmente la clase de complejidad fundamental de algoritmos simples [Evaluar]
4. Desarrollar estudios empíricos para determinar y validar hipótesis sobre la complejidad de tiempo de ejecución de varios algoritmos ejecutando algoritmos con entradas de varios tamaños y comparando el rendimiento real con el análisis teórico [Crear]
5. Explicar ejemplos que ilustren los compromisos tiempo-espacio de algoritmos [Explicar]
6. Explicar cómo el balance del árbol afecta la eficiencia de las operaciones de árbol de búsqueda binaria [Explicar]