2022-03-28

Recursos que queremos optimizar

• Tiempo de ejecución
• Memoria
• Otros... (de los cuales no nos vamos a ocupar en esta materia)

Complejidad Algorítmica

• ¿Cómo medimos la complejidad algorítmica?

  • Forma empírica o experimental:

    Medir el tiempo de ejecución para una determinada entrada y en una computadora concreta, usando un cronómetro o analizando el consumo de recursos de la computadora.

  • Forma teórica:

    Medida teórica del comportamiento de un algoritmo. Se puede calcular/estimar a priori de la ejecución.

Ventajas del enfoque teórico

• Capacidad de hacer el análisis a priori
• Vale para todas las instancias del problema
• Es independiente del lenguaje de programación utilizado
• Es independiente del dispositivo utilizado para ejecutar el algoritmo
• Es independiente de la pericia del programador

Análisis Teórico

• Basado en un modelo de cómputo consensuado: modelo ideal de máquina sobre el cual acordamos sus características. La medida de complejidad estará asociada a este modelo de cómputo y así nos abstraemos de los dispositivos y procesadores particulares.
• En función del tamaño del input: esto es lo que hace que el análisis valga para toda instancia del mismo problema.