Introducción a análisis asintótico
Clase 10 de 18 • Curso de Complejidad Algorítmica con JavaScript
Resumen
La asíntota es una recta que se aproxima lo máximo posible a una función, pero nunca llegan a cruzarse.
Análisis asintótico
El análisis asintótico consiste en modelar nuestros algoritmos en una representación gráfica de su comportamiento limitante. Recordarás que los datos arrojados en el cálculo de la eficiencia del algoritmo no eran iguales en cada ejecución.
Para evitar esto se modela una función capaz de representar el algoritmo a partir de sus procesos en función de la cantidad de entradas, que se aproxime al comportamiento real.
Mientras la asíntota sea más vertical, la curva de la función de nuestro algoritmo necesitará muchos más recursos por pocos elementos de entrada, es decir, ocupará demasiado espacio o tiempo del necesario.
Como puedes ver en la siguiente gráfica, estas curvas son las que debemos evitar y mantener una asíntota lo más horizontal posible. No te preocupes de la representación, lo veremos en la siguiente clase.
Fuente: Big-O Cheat Sheet
Existen varios tipos de funciones: constante, lineal, polinomial, logarítmica y exponencial.
Contribución creada por Andrés Guano (Platzi Contributor).