2.2.5 AL/Marco de Análisis de Complejidad

Temas:
Core

• 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
• Mediciones empíricas de rendimiento
• Compromisos tiempo-espacio en algoritmos

Aprendizaje esperado (Learning Outcomes):
Core:

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]