5.20.4.6 Notación Asintótica y Clases de Complejidad (4 horas) [Habilidades AG-C08,AG-C12]

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

Temas

1. Análisis de complejidad asintótica (cotas promedio y peor caso):
   1. Notaciones formales Big-O, Big-Omega y Big-Theta
   2. Clases de Complejidad Fundamentales y Ejemplos/Problemas Representativos:
      1. $O(1)$ Constante (por ejemplo, acceso a arreglo)
      2. $O(\log_2 n)$ Logarítmica (por ejemplo, búsqueda binaria)
      3. $O(n)$ Lineal (por ejemplo, búsqueda lineal)
      4. $O(n \log_2 n)$ Log Lineal (por ejemplo, mergesort)
      5. $O(n^2)$ Cuadrática (por ejemplo, ordenamiento por selección)
      6. $O(n^c)$ Polinomial (por ejemplo, $O(n^3)$ eliminación gaussiana)
      7. $O(2^n)$ Exponencial (por ejemplo, Mochila, Satisfactibilidad (SAT), Viajante de Comercio (TSP), todos los subconjuntos)
      8. $O(n!)$ Factorial (por ejemplo, circuito hamiltoniano, todas las permutaciones)

Aprendizaje esperado (Learning Outcomes)

1. Usando ejemplos, explicar cada una de las clases de complejidad fundamentales en esta unidad [Explicar]
2. Para cada clase de complejidad fundamental en esta unidad, explicar un algoritmo que demuestre la complejidad de tiempo de ejecución asociada [Explicar]
3. Explicar a una audiencia no técnica la importancia de los algoritmos tratables versus intratables usando una explicación intuitiva de la complejidad Big-O [Explicar]
4. Aplicar la notación Big-O para dar cotas superiores en la complejidad tiempo/espacio de algoritmos [Aplicar]