2.2.6 AL/Notación Asintótica y Clases de Complejidad

Temas:
Core

• 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):
Core:

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]