Repaso de Complejidad Algorítmica y Notación Big-O
Contenido del curso
Complejidad algorítmica
Análisis asintótico
Recomendaciones
Bonus
Repaso de Complejidad Algorítmica y Notación Big-O
Contenido del curso
Repaso de Complejidad Algorítmica y Notación Big-O
¡Hola! Esta es la lectura final del Curso de Complejidad Algorítmica. Si ya te sientes preparado puedes directamente pasar el examen, pero si quieres estar seguro/a de que todo está en orden, pues he preparado esta lectura para que repasemos los conceptos que hemos aprendido. 👇
⏲ Cuando esperas a que cargue una aplicación web o cuando una pestaña de un navegador ocupa mucho espacio, estamos consumiendo recursos como tiempo o espacio.
📈 Los algoritmos que se ejecutan al realizar acciones pueden ser medibles en la notación Big-O.
👩💻 Para calcular la notación Big-O aplicamos una serie de reglas a través de nuestro código.
📏 Reglas para estructuras
Las reglas para Big-O en tiempo son:
Las reglas para Big-O en espacio son:
Y siempre debemos simplificar la notación:
Hasta aquí tenemos todas las conclusiones del curso. Pero recuerda que también ahondamos en el por qué de cada concepto.
¿Por qué necesitamos Big-O? ¿Por qué una notación?
Un algoritmo o un programa podrían ejecutarse en cinco o diez horas, incluso si hablamos de una o varias computadoras. Big-O viene a poner orden todo eso, dándonos una forma fácil de leer en la que podemos determinar la eficiencia de un algoritmo.
¿Por qué asignamos Big-O a cada estructura?
Big-O medirá el recurso generado respecto a la entrada del algoritmo. Y las estructuras son un aspecto sencillo de convertir en medición de recursos.
Por ejemplo:
Con los bucles es sencillo, los bucles repiten instrucciones, y al repetir toman más tiempo en la computadora.
Con los arreglos es igual, repiten una serie de elementos, y al repetir esos elementos toman más espacio de la computadora.
¿Por qué nos quedamos con el grado mayor al simplificar Big-O?
En Big-O queremos comprender qué tanto recurso (como tiempo o espacio) nos gasta un algoritmo cuándo aumentamos los datos. Y cada grado aumenta a un ritmo totalmente distinto.
Por ejemplo n crece más que 1000:
No es necesario quedarnos con los grados pequeños: Podemos simplificar y quedarnos con lo importante.
¿Solo hay Big-O para espacio y tiempo?
No, la complejidad es el estudio de los recursos que utilizan los algoritmos. Estos recursos pueden ser cualquier concepto de hardware y software. Como acceso a la memoria, comparaciones de condiciones, o lo que se necesite limitar.
La buena noticia de esto, es que no se requiere inventar nuevas notaciones. Big-O es suficiente para que personas como tú, desarrolladores/as de software o científicos/as de computación trabajen sobre esto.
¡Esto es todo!
Esta lectura fue un resumen de todo lo que hemos encontrado en este curso.
Sin embargo los porqués y cómos nunca se acaban con un campo de estudio tan interesante como el de la complejidad. Así que, no dudes en usar el sistema de preguntas con los temas que hemos tratado aquí, o incluso temas más profundos de la Teoría de la Complejidad si tienes más curiosidad.
🎉 Ahora la complejidad es tuya, no del examen. ¡Ve a darlo! 😎
Camilo Cadavid Cardona
Estudiante
Anfernee Valera
Estudiante
Luis Rogelio Reyes Hernandez
Estudiante
Enrique Aguilera
Estudiante
Jean Nuñez
Estudiante
ENRIQUE NIETO MARTINEZ
Estudiante
Tania Sosa
Estudiante
Daniel Omar Hernández Muñoz
Estudiante
David Molina
Estudiante
Marcelo Arias
Profesor
José Eduardo Vinagre de Dios
Estudiante
Bryan Castano
EstudianteTodo esto me hace concluir que los frameworks mas comunes en Javascript terminan haciendo que nuestro código consuma muchos mas recursos en memoria y en tiempo.
Por otra parte, el código en vainilla JS en ocasiones te limitan y no te permiten desarrollar los mismos productos que con los frameworks.
Entonces, qué importa mas? tu proyecto hecho en x framework que te gasta poco tiempo desarrollando pero instalaste una cantidad de código del cual solo conoces el 5% ó tu proyecto hecho en vainilla js que te gasta mucho mas tiempo en lograr el resultado pero pesa mucho menos y corre mejor...
Es solo un comentario... no creo que haya una respuesta, habrán puntos de vista...
Estoy de acuerdo contigo, no creo que exista una respuesta como tal. Hay opiniones y decisiones que pueden valer más o menos, según tus circunstancias. Es entonces cuando pienso que la responsabilidad de nuestro criterio es importante, ya que desde este punto de vista podemos tomar las mejores decisiones para el desarrollo de nuestro proyecto.
Un framework suele ocurrir que consuman más que JS plano, pero es un peso que se suele tolerar por 2 cosas muy importantes: Mantenibilidad y Tiempo
Mantenibilidad porque en equipos de 100 personas escribiendo vanilla JS, es casi imposible que todos sigan un estándar de programación sin utilizar algún framework que los obligue a programar de cierta forma.
Tiempo el tiempo es el recurso no renovable más valioso que existe, los frameworks nos dan muchísimas herramientas que nos ayudan a entregar mejores productos más rápido. Además, decidir entre tener una aplicación que funciona al 60% de eficiencia hecha con un framework en 1 mes VS una aplicación que funciona al 100% de eficiencia super optimizada hecha en vanilla pero tomo más de 1 año hacerla. Se escogería entregar en el 1 mes con un framework porque programando es extremadamente difícil saber si tu producto o solución realmente atiende el mercado que quieres o realmente soluciona el problema planteado. por lo cual irónicamente es más importante generar un MVP que generar un buen MVP.
Deberían de hacer estos resumenes al final de cada curso Este esta muy bueno
Ufff que bueno info
Estaría genial otro curso sobre esto donde veamos Big Omega y Big Theta. ¿Qué opinan?
¡Hola Enrique! 😄
Es una excelente sugerencia, la tendremos en cuenta para futuros cursos.
¡Nunca pares de aprender! 💚
Ufff Ufff Ufff, esto es lo que yo buscaba, que belleza, que belleza señores!!
Oigan, alguien sabe si hay alguna forma en la que el análisis asintótico se pueda hacer de forma automática? y si no lo hay porque? Pregunto porque me parece que las reglas están bien establecidas, tengo un for entonces O(n), tengo un for anidado entonces O(n*2), y así sucesivamente, entonces parece sencillo tener un algoritmo que mida la complejidad algorítmica.
¡Hola David! Gran pregunta.
Existen algunos esfuerzos para crear una herramienta cómo la que describes. Aún así quedaría por resolver un problema complicado, y es que cualquier lenguaje tiene varias formas en las que podría definir un bucle (tenemos método como .map que iteran como un bucle).
Otra herramienta que me gusta mucho, es big_o para Python que no verifica textualmente el código, sino que hace un análisis asintótico midiendo el tiempo de cada ejecución, incrementando el tamaño de entrada y estimando el resultado en notación Big-O en base a todas las mediciones de tiempo marcadas.
En JavaScript sería como utilizar performance.now() cada vez que ejecutemos un algoritmo al incrementar su tamaño de entrada. Y luego intentar colocarlo bajo alguna forma de crecimiento.
Falto ver un ejemplo donde la complejidad fuera logaritmica.
My Pregunta es . Cual Seria La Complejidad deL Algoritmo Recursivo de Fibonacci TOP_DOwn Approach sin Memoization , Este Sera O ( 2**n ) || O ( n! ) , es por algo del Stack de Memoria de las LLamadas Recursivas que se acumulan com oStack [ FiFO ] en la Memoria de PC mientas se alcanza el caso base . cual es sera la compleidad de eso? Yo aun me lo Pregunto ? . \n