Análisis de Complejidad de Algoritmos: Tiempos y Eficiencia
Clase 6 de 18 • Curso de Complejidad Algorítmica con JavaScript
Resumen
La complejidad temporal es la cantidad de tiempo en el que un algoritmo tarda en ejecutarse. En otras palabras, cómo el algoritmo aumenta en el tiempo, con respecto a la cantidad de elementos de entrada que debe procesar.
Comparación de algoritmos
Comparemos dos algoritmos que resuelven un mismo problema: “Astronauta” y “Experto”. El primer algoritmo aumenta su tiempo de ejecución mientras más estudiantes sean ingresados. El tiempo de ejecución del segundo permanece constante.
Aunque ambos algoritmos resuelven el mismo problema, manejan sus tiempos de ejecución de manera diferente a medida que procesa más elementos.
La siguiente gráfica muestra el tiempo de ejecución en función de la cantidad de elementos a procesar (inputs).
El algoritmo “Astronauta” tiene una tendencia lineal, es decir, mientras más elementos ejecute, más tiempo necesitará el programa.
El algoritmo “Experto” es constante, es decir, ejecuta la aplicación en el mismo tiempo para cualquier valor de elementos a procesar.
Por lo tanto, la complejidad no trata de cuántos segundos, aproximadamente, se tarda un algoritmo en ejecutar, sino de cómo aumenta el tiempo cuando existe una mayor o menor cantidad de elementos a procesar.
Contribución creada por Andrés Guano (Platzi Contributor).