4.20.2.1 Análisis Básico (10 horas) [Habilidades C1]

Referencias Bibliográficas: [Kleinberg and Tardos, 2005,Dasgupta et al., 2006,Rivest and Stein, 2009,Sedgewick and Flajolet, 2013,Knuth, 1997a] 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. Uso de la notación Big O.
6. Relaciones recurrentes.
7. Análisis de algoritmos iterativos y recursivos.
8. Teorema Maestro y Árboles Recursivos.

Objetivos de Aprendizaje

1. Explique a que se refiere con “mejor", “esperado" y “peor" caso de comportamiento de un algoritmo [Evaluar]
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]
3. Determine informalmente el tiempo y el espacio de complejidad de diferentes algoritmos [Evaluar]
4. Indique la definición formal de Big O [Evaluar]
5. Lista y contraste de clases estándares de complejidad [Evaluar]
6. Use la notación formal de la Big O para dar límites superiores asintóticos en la complejidad de tiempo y espacio de los algoritmos [Evaluar]
7. Usar la notación formal Big O para dar límites de casos esperados en el tiempo de complejidad de los algoritmos [Evaluar]
8. 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 [Evaluar]
9. Usar relaciones recurrentes para determinar el tiempo de complejidad de algoritmos recursivamente definidos [Evaluar]
10. Resuelve relaciones de recurrencia básicas, por ejemplo. usando alguna forma del Teorema Maestro [Evaluar]