Complejidad Algorítmica sin llorar - Notación Big O

Summary

Este vídeo explica de manera clara y entretenida qué es la complejidad algorítmica, abordando tanto la complejidad en espacio como en tiempo. A través de ejemplos sencillos, como ordenar una lista de números aleatorios, se muestra cómo medir los recursos que un algoritmo necesita. Se introduce la notación Big O para describir la cota superior asintótica, destacando cómo entender los diferentes órdenes de complejidad: constante, lineal, cuadrático y más. Además, se enfatiza la importancia de elegir algoritmos eficientes según el tamaño de la entrada, usando comparaciones visuales para ilustrar su impacto en el rendimiento. ¡Una forma divertida de comprender un tema crucial en la programación!

Takeaways

• 😀 La complejidad algorítmica mide los recursos (como tiempo y espacio) que un algoritmo necesita en relación con el tamaño de la entrada.
• 😀 La complejidad en espacio se refiere a la cantidad de memoria que un algoritmo requiere durante su ejecución.
• 😀 Un algoritmo que usa dos listas auxiliares para ordenar aleatoriamente tiene una complejidad de espacio de O(2n), mientras que uno que solo usa un elemento tiene una complejidad de O(1).
• 😀 La notación Big O (O grande) se usa para describir la cota superior asintótica, es decir, el máximo crecimiento que puede tener una función en términos de su tamaño de entrada.
• 😀 Un algoritmo de orden lineal, como el que recorre una lista y realiza operaciones básicas en cada elemento, tiene una complejidad de O(n).
• 😀 En un algoritmo que compara elementos entre dos listas, la complejidad puede ser cuadrática (O(n^2)), ya que cada elemento de la primera lista se compara con todos los elementos de la segunda lista.
• 😀 La notación Big O se usa para describir el caso peor de un algoritmo, ya que siempre nos interesa el máximo número de operaciones posibles.
• 😀 La complejidad cuadrática (O(n^2)) implica que el número de operaciones crece rápidamente a medida que aumenta el tamaño de la entrada.
• 😀 En el caso de un algoritmo que busca repeticiones entre dos listas, su comportamiento depende de si encuentra repeticiones o no, lo que puede generar una diferencia entre el caso peor (O(n^2)) y el mejor (O(1)).
• 😀 Existen diferentes órdenes de complejidad algorítmica, como el constante, logarítmico, lineal, cuadrático y exponencial, siendo este último uno de los más costosos en términos de tiempo de ejecución.
• 😀 Los algoritmos con complejidad exponencial son ineficientes para problemas grandes, ya que el tiempo de ejecución se vuelve astronómico, como en el caso de algoritmos factoriales.

Q & A

¿Qué mide la complejidad algorítmica de un algoritmo?

La complejidad algorítmica mide los recursos que un algoritmo necesita en función del tamaño de la entrada, normalmente en tiempo o espacio.

¿Qué es la complejidad en espacio?

La complejidad en espacio es la cantidad de memoria que necesita un algoritmo durante su ejecución.

¿Cuál es la diferencia entre los dos algoritmos presentados en el video en cuanto a uso de memoria?

El primer algoritmo utiliza dos listas auxiliares, lo que significa que su complejidad en espacio es O(2n), mientras que el segundo algoritmo utiliza solo un elemento extra en memoria, lo que le da una complejidad en espacio O(1).

¿Qué significa la notación Big O?

La notación Big O indica el orden de complejidad de una función, específicamente la cota superior asintótica, que describe cómo crece la función a medida que aumenta el tamaño de la entrada.

¿Cómo se calcula la cota superior asintótica de una función?

Para calcular la cota superior asintótica, se identifica el término más significativo de la función y se elimina la constante. Esto permite determinar el comportamiento de crecimiento de la función a medida que la entrada crece.

¿Cuál es la diferencia entre Big O, Big Omega y Big Theta?

Big O se refiere a la cota superior, es decir, el comportamiento máximo de una función. Big Omega se refiere a la cota inferior, y Big Theta describe el comportamiento ajustado, es decir, tanto la cota superior como la inferior de la función.

¿Qué es una operación básica en el análisis de algoritmos?

Una operación básica es una acción simple realizada por el algoritmo, como acceder a un elemento de una lista, realizar una operación aritmética o hacer una comparación entre elementos.

¿Cómo se mide la complejidad temporal de un algoritmo?

La complejidad temporal se mide analizando el número de operaciones básicas que el algoritmo realiza en función del tamaño de la entrada. Cada operación básica cuenta como una unidad de trabajo.

¿Qué tipo de complejidad tiene el algoritmo que recorre una lista y suma 1 a cada elemento?

El algoritmo que recorre una lista y suma 1 a cada elemento tiene una complejidad temporal O(n), ya que realiza una operación básica por cada elemento de la lista.

¿Por qué un algoritmo de búsqueda de repeticiones en dos listas tiene una complejidad O(n^2)?

El algoritmo de búsqueda de repeticiones tiene una complejidad O(n^2) porque recorre cada elemento de la primera lista y, para cada uno, recorre toda la segunda lista, lo que resulta en n * n iteraciones.