Versión borrador / preliminar
Este documento es una versión preliminar para uso interno. Si encuentra algún problema o error, o si tiene algún comentario por favor repórtelo a los autores.
Nociones de complejidad#
Objetivo de la sección
El objetivo de esta sección es …
por qué estudiar complejidad: tiempo, memoria, energía
Número de operaciones y tiempo#
Medir tiempos en Python#
Formas básicas#
Algoritmos constantes#
pop
Algoritmos lineales#
buscar cuántos valen X
Algoritmos cuadráticos#
buscar cuántas parejas sumadas valen X
Algoritmos cúbicos#
buscar cuántas tripletas sumadas valen X
Visión global#
Algoritmos logarítmicos#
búsqueda binaria
Algoritmos exponenciales#
TSP
Reglas básicas#
constantes
mayor predomina
OJO: las librerías cuentan!
Complejidad en memoria#
Por qué es importante
Uso de memoria constante#
mayor
Uso de memoria lineal#
contar repetidos
OJO: trampa de dict
Ejercicios#
Construya …
En un …
Más allá de Python#
Además de …