Notación Big O | Análisis de algoritmos de forma sencilla
Summary
TLDREste video educativo explica la importancia de la eficiencia en los programas y cómo se mide. Se introduce la anotación de Big O, una herramienta para analizar y comparar la complejidad de algoritmos en términos de su rendimiento y uso de recursos. A través de ejemplos sencillos, como llevar libros a un amigo, se ilustra cómo diferentes métodos pueden tener un impacto variado en el tiempo de ejecución. Se explora la notación asintótica para simplificar y comparar el crecimiento de la eficiencia de los algoritmos, y se detallan los conceptos de Big O constantes, lineal, cuadrático y exponencial. El video concluye con un análisis práctico del algoritmo de ordenamiento por inserción, demostrando cómo se determina su complejidad de tiempo cuadrática.
Takeaways
- 😀 La eficiencia de los programas es crucial, similar a cómo un arquitecto necesita saber el peso soportable de un edificio o un panadero cuántas rosquillas puede hacer en una hora.
- 🕵️♂️ Para medir la eficiencia de un algoritmo, se puede analizar tanto su uso de memoria como su velocidad de ejecución, pero en este vídeo se enfoca en la velocidad.
- ⏱️ La medición directa del tiempo de ejecución de un programa no es siempre fiable, ya que el rendimiento puede variar dependiendo de la entrada y otros factores.
- 📚 Se utiliza la notación asintótica para simplificar y comparar cómo crece el tiempo de ejecución de un algoritmo con respecto a su entrada.
- 📊 La notación big O (O grande) es especialmente útil para representar el comportamiento en el peor de los casos, lo que es comúnmente de interés para desarrolladores.
- 🔢 Las complejidades de tiempo comunes incluyen O(1) para tiempo constante, O(n) para tiempo lineal, O(n^2) para tiempo cuadrático, y así sucesivamente.
- 🔄 La complejidad de un ciclo se determina por la cantidad de veces que se ejecuta, que a su vez depende de la entrada del programa.
- 🔗 Cuando hay ciclos anidados, la complejidad de tiempo es el producto de las complejidades de los ciclos individuales.
- 🌐 En el caso de condicionales dentro de ciclos, se considera el peor caso para determinar la complejidad de tiempo.
- 📝 Al analizar la complejidad de un algoritmo, se suman las complejidades de todas las secciones del código y se simplifica al término más significativo.
- 🧩 El análisis de la complejidad de tiempo se ejemplifica con el algoritmo de inserción sort, donde se determina que su complejidad es O(n^2).
Q & A
¿Qué es la anotación de Vigo y cómo se relaciona con la eficiencia de los programas?
-La anotación de Vigo es una forma de analizar la complejidad de un algoritmo, esencial para entender cuán eficiente es un programa. Se utiliza para determinar el tiempo o la cantidad de recursos que un algoritmo necesita para ejecutarse en función de la entrada.
¿Cuál es la diferencia entre analizar la eficiencia de memoria y la velocidad de un algoritmo?
-La eficiencia de memoria se refiere a cuánto espacio en la memoria un algoritmo utiliza, mientras que la velocidad se refiere a cuánto tiempo toma un algoritmo para completar una tarea. En el guion, se enfoca en la velocidad, es decir, el tiempo de ejecución.
¿Por qué no es suficiente simplemente ejecutar un programa para medir su eficiencia?
-Ejecutar un programa una vez no es suficiente porque el tiempo de ejecución puede variar dependiendo de la entrada. Un algoritmo puede tener un tiempo de ejecución que escala de manera diferente con la entrada, lo que requiere un análisis más profundo utilizando la anotación de Vigo.
¿Qué ejemplo se utiliza en el guion para explicar cómo el tiempo de ejecución de un algoritmo puede variar con la entrada?
-Se utiliza el ejemplo de llevar libros a un amigo. Un método es llevar todos los libros en un carro, que toma el mismo tiempo independientemente de la cantidad de libros, lo que es constante (Vigo de 1). El otro método es correr con un libro a la vez, lo que toma más tiempo si se llevan más libros, lo que es lineal (Vigo de n).
¿Qué es la notación asintótica y cómo ayuda a clasificar el comportamiento de los algoritmos?
-La notación asintótica es una forma de simplificar y comparar la tasa de crecimiento de funciones, lo que permite clasificar cómo crece el tiempo de ejecución de un algoritmo con respecto a la entrada. Se utiliza para describir el comportamiento de los algoritmos en términos de su complejidad temporal.
¿Qué significa Vigo de uno, Vigo de n, Vigo de n al cuadrado, y por qué son importantes?
-Vigo de uno (O(1)) significa que el tiempo de ejecución no varía con la entrada. Vigo de n (O(n)) indica que el tiempo de ejecución crece linealmente con la entrada. Vigo de n al cuadrado (O(n^2)) indica que el tiempo de ejecución crece cuadráticamente con la entrada. Estos términos son importantes porque describen cómo escala el rendimiento de un algoritmo a medida que crece la entrada.
¿Cómo se determina la complejidad de un ciclo en términos de Vigo?
-La complejidad de un ciclo se determina por la cantidad de veces que se ejecuta en relación con la entrada. Si un ciclo se ejecuta una vez por cada elemento de la entrada, es Vigo de n. Si hay ciclos anidados, la complejidad será el producto de las complejidades de cada ciclo, como en el caso de dos ciclos anidados, que sería Vigo de n al cuadrado.
¿Qué pasa con la complejidad de un algoritmo cuando hay condicionales dentro de los ciclos?
-Cuando hay condicionales dentro de los ciclos, se considera el peor caso para determinar la complejidad. Se asume que el algoritmo tomará la ruta que resulte en el mayor número de operaciones, lo que puede incrementar la complejidad temporal.
¿Cómo se analiza la complejidad de un algoritmo recursivo?
-La complejidad de un algoritmo recursivo se analiza de manera diferente a la de algoritmos iterativos. Se requiere de técnicas especiales para manejar la complejidad debido a la naturaleza de llamadas recursivas y cómo estas afectan al tiempo de ejecución.
¿Cómo se determina la complejidad de un algoritmo de inserción sort basado en el análisis del guion?
-El algoritmo de inserción sort se ejecuta en Vigo de n al cuadrado (O(n^2)) porque el ciclo exterior recorre la entrada n veces y el ciclo interior se ejecuta en función del número de elementos previos que ya están ordenados, lo que en el peor caso es n/2 veces.
Outlines
🕵️♂️ Análisis de la eficiencia de algoritmos
Este párrafo introduce la importancia de medir la eficiencia de los programas, similar a cómo un arquitecto necesita saber el peso que soporta un edificio o un panadero cuántas rosquillas puede hacer en una hora. Se menciona que para entender cómo se comporta un algoritmo, no siempre es necesario ejecutarlo, ya que se puede analizar su complejidad utilizando la anotación de Vigo. El vídeo se centra en cómo analizar la velocidad de un algoritmo, y se explica que la ejecución del programa no es sencilla ya que el tiempo de ejecución escala de manera diferente con la entrada. Se usan ejemplos prácticos para ilustrar cómo el tiempo de ejecución puede variar dependiendo de la complejidad del algoritmo, y se menciona la notación asintótica para clasificar la eficiencia de los algoritmos.
🔍 Clasificación de la complejidad de algoritmos
En este párrafo se profundiza en la clasificación de la complejidad de los algoritmos a través de la notación asintótica. Se describen diferentes tipos de complejidad como constante, lineal, cuadrática, logarítmica, etc., y se explica cómo estos se relacionan con el comportamiento del algoritmo frente a diferentes entradas. Se menciona que la anotación de Vigo permite simplificar la representación de la tasa de crecimiento de un algoritmo, permitiendo así comparar y predecir su rendimiento. Se enfatiza en el uso del límite superior (big O) para analizar el peor caso del comportamiento de un algoritmo, lo cual es de mayor interés para los desarrolladores al diseñar y optimizar programas.
🛠 Análisis práctico de la complejidad de Insertion Sort
Este párrafo presenta un análisis práctico de la complejidad de un algoritmo de ordenamiento conocido como Insertion Sort. Se describe el proceso de análisis de la complejidad de acuerdo con la anotación de Vigo, tomando en cuenta cuántas veces se ejecutan diferentes partes del código en relación con la entrada. Se detallan los ciclos y condiciones que afectan la complejidad, y se calcula que el algoritmo tiene una complejidad de O(n^2). Se resalta la importancia de simplificar la complejidad al término más significativo para entender mejor el rendimiento del algoritmo.
Mindmap
Keywords
💡Eficiencia
💡Complejidad de un algoritmo
💡Anotación de Vigo
💡Tiempo de ejecución
💡Constante (V-1)
💡Lineal (V-n)
💡Ciclos anidados
💡Peor caso
💡Logaritmo (V-log n)
💡Insertion Sort
Highlights
La importancia de conocer la eficiencia de los programas, comparándola con la necesidad de un arquitecto o un panadero de conocer sus límites.
La necesidad de medir la velocidad de un algoritmo para responder preguntas de clientes sobre rendimiento.
La diferencia entre analizar el uso de memoria y la velocidad de un algoritmo, y el enfoque en la velocidad en este vídeo.
La limitación de medir el tiempo de ejecución simplemente ejecutando el programa, debido a que la entrada puede afectar el tiempo de ejecución.
El ejemplo de llevar libros a un amigo para ilustrar cómo el tiempo de ejecución de un algoritmo puede variar según la entrada.
La introducción de la notación asintótica para clasificar cómo crecen los algoritmos según la entrada.
La explicación de que la notación asintótica simplifica las funciones de crecimiento de un algoritmo.
La preferencia por el límite superior en la notación big O, que representa el peor caso del comportamiento del algoritmo.
La definición de diferentes complejidades de algoritmos como big O(1), big O(n), big O(n^2), big O(log n), etc.
Cómo analizar el código para determinar la complejidad de un algoritmo, teniendo en cuenta ciclos, condicionales y llamadas a funciones.
La regla de que cualquier función o línea de código que no sea un ciclo se considera big O(1).
La complejidad de ciclos anidados y cómo se determina basándose en cuántas veces se ejecuta el ciclo interno.
La consideración de condicionales dentro de ciclos y cómo se toma el peor caso para la anotación big O.
El proceso de sumar las complejidades de diferentes secciones de código y simplificarlas al término más significativo.
El análisis práctico del algoritmo de inserción sort, incluyendo la complejidad de ciclos y operaciones dentro de ellos.
La conclusión de que la complejidad del algoritmo de inserción sort es big O(n^2).
El llamado a la participación de los espectadores para comentar, compartir y suscribirse para recibir más contenido similar.
Transcripts
sabemos que es muy importante conocer
qué tan eficientes son nuestros
programas es lo equivalente a que un
arquitecto conozca cuánto peso aguanta
un edificio o que un panadero sepa
cuántas rosquillas puede hacer en una
hora nuestros clientes seguramente nos
van a preguntar ese tipo de cosas oye
cuando te vas a tardar en procesar todos
los documentos cuántas transacciones por
segundo aguanta tu aplicación cuántos
usuarios puedes manejar qué tanta
memoria ocupa cuántos servidores voy a
necesitar para aguantar este tráfico y
para que nosotros nos demos cuenta cómo
se comporta un algoritmo no tenemos por
qué siempre ejecutarlos para ver el
resultado muchas veces podemos
analizarlos y determinar su complejidad
utilizando la anotación de vigo o en
este vídeo justamente vamos a ver de qué
se trata y cómo podemos utilizarlo para
analizar nuestros algoritmos soy yo y
bienvenido archivo code
[Música]
bueno
para empezar hay que diferenciar qué es
lo que podemos analizar y por ende ver
qué tan bueno es un algoritmo y podemos
hacerlo desde dos perspectivas la
primera es el uso de la memoria y la
segunda la velocidad qué tan rápido es
por hoy vamos a enfocarnos en la
velocidad y cómo es que puedo medirla
pues podemos simplemente ejecutar
nuestro programa contar cuántos segundos
se tarda y ya está el detalle es que no
es tan sencillo recuerdan que un
algoritmo es una secuencia de pasos que
toman una entrada y generan una salida
bueno pues qué tal si la segunda vez que
estoy ejecutando mi programa para medir
el tiempo la entrada es el doble de
grande entonces se va a tardar el doble
de tiempo no la verdad es que no
dependiendo del algoritmo el tiempo de
ejecución escala diferente con la
entrada y esto es más fácil de explicar
con un ejemplo imagínate que quiero
llevarle unos libros a mi amigo es tema
que vive aquí a una cuadra de mi casa y
tengo dos métodos para hacerlo el
primero es tomar los libros que quieran
ponerlos en mi carro y manejar hasta
allá
no importa cuántos libros quiera
llevarles siempre me tardo lo mismo
digamos 5 minutos quiero llevar un libro
cinco minutos dos libros cinco minutos
veinte libros cinco minutos sin importar
la entrada en este caso el número de
libros el tiempo que me tardo no varía
es constante y el segundo método que
puedo usar es tomar el libro y correr
hacia su casa y con eso me tardo más o
menos tres minutos sin tener que dar
todas las vueltas en el carro pero
solamente puedo llevar un libro a la vez
así que si quiero llevar dos tendré que
dar dos vueltas y ahora me tardaría seis
minutos así que vivar tres son nueve
minutos y así va escalando el tiempo que
me tardé dependiendo de cuántos libros
quiera llevar o dependo de mi entrada en
este segundo método del tiempo crece de
forma lineal y de la misma manera puede
idear otros métodos para mandarle libros
y cada uno puede crecer de manera
diferente y para poder clasificar todas
estas diferentes formas en que crecen
los algoritmos dependiendo de la entrada
usamos la notación asintótica
notaciones sintética no ibas a hablar de
vigo sí y es que vigo es una anotación
es sintética verás que estas gráficas
que muestran cuánto tiempo se tarda un
programa en ejecutarse con base a la
entrada en la vida real no son tan
bonitas hay muchas cosas que afectan la
ejecución de un programa ya en una
computadora y aunque sea el mismo
programa con la misma entrada cuando
ejecutas dos o más veces nunca va a ser
exactamente igual y estas funciones
terminan siendo mucho más complejas así
que lo que nos permite la anotación
asintótica es poder simplificar estas
funciones que representan la tasa de
crecimiento de un algoritmo es como si
tomáramos un número con decimales y lo
redondeamos y así como redondear el
número podemos hacerlo hacia arriba o
hacia abajo también hay diferentes
notaciones asintóticas que podemos
utilizar dependiendo de qué es lo que
nos interesa si algún límite superior o
un límite inferior o los dos
ok pero nosotros como desarrolladores lo
que más nos interesa y lo que más
terminamos usando es el límite superior
la anotación de vieja o por qué porque
es el límite representa el
comportamiento en el peor de los casos y
eso normalmente es lo que más nos
interesa no es lo mismo que te diga que
esta silla soporta más de 50 kilos que
tantos más 80 100 200 para sentar un
elefante aquí me es más útil conocer qué
máximo llega a 150 y ya en base a eso
saber cómo poder manejar esta silla o mi
algoritmo y recuerden que con esta
anotación del big joe estamos tratando
de identificar cómo se comportan nuestro
algoritmo dependiendo de la entrada así
podemos clasificar nuestros programas
con diferentes complejidades vigo de uno
para definir qué es constante que no
varía dependiendo de la entrada vigo de
n donde n normalmente representa la
entrada y eso significa que está
creciendo de manera lineal vigo de n al
cuadrado de logaritmo de n de en el
logaritmo de n 2 a la n etcétera esto lo
que nos dice es que si mi algoritmo es
en al cuadrado entre más
a la entrada peor se va a comportar y si
esa misma entrada la pongo en un
algoritmo que sea solamente logaritmo de
n se va a comportar muchísimo mejor que
mi solución en al cuadrado y entonces
cómo podemos analizar nuestro código
para determinar cuál es su complejidad
bueno cualquier función o línea de
código se considera vigo de uno o tiempo
constante siempre y cuando no sea un
ciclo no tenga recursos o no sea una
llamada a una función que a su vez no
sea de tiempo constante si es el tiempo
constante pues sigue siendo tiempo
constante ahora yéndonos a los ciclos se
considera vivo de n o tiempo lineal
cuando la variable del ciclo va
incrementando o incrementando por un
número constante o sea que vaya subiendo
de uno en uno o de dos en dos o de tres
en tres
etcétera y siempre y cuando este ciclo
vaya y tirando en base a la entrada que
vaya recorriendo los números que
nosotros le pasamos o vaya recorriendo
los caracteres del string o que vaya
haciendo algo con la entrada si ese
ciclo
tres veces y siempre y teherán tres
veces independientemente de la entrada
que le pusimos se sigue considerando
tiempo constante vigo out de uno y
cuando tenemos ciclos anidados la
complejidad depende de cuántas veces se
ejecuta el ciclo que está más adentro
llegando a bigote en al cuadrado si son
dos ciclos o si son tres ciclos n al
cubo en la cuatro en las cinco depende
de cuántos ciclos alineados tengamos
dentro y si todos esos ciclos también y
teherán basándose en la entrada en la
entrada o en variables que a su vez
están basándose en la entrada ahora si
la variable del ciclo en lugar de estar
incrementando por un número constante va
multiplicándose o dividiéndose esta
complejidad se convierte en logaritmo de
n iia así de plano va incrementándose de
forma exponencial entonces se considera
logaritmo del logaritmo de n bueno y qué
pasa si tenemos condicionales adentro de
los ciclos y ahí recuerden que estamos
calculando vic o que es el
comportamiento en el peor de los casos
así que
cuando nos topamos con ese if tomamos la
decisión de entrar o de saltarnos los
dependiendo de cuál nos vaya a ser
ejecutar el mayor número de líneas la
decisión que nos lleve por la peor ruta
que nos haga tomar el peor caso y una
vez que hayamos ya calculado esto de
diferentes secciones con diferentes y
llamadas al sistema etcétera lo que
hacemos es sumar todas esas
complejidades y simplificarlo recuerden
que la anotación es sintética se trata
de simplificar así que de la suma que
nos haya quedado vamos a tomar solamente
el término más significativo o sea el
cachito que sea el más grande quitando
cualquier constante un número que esté
multiplicando al valor de n para que así
nos quede alguna complejidad de las que
ya conocemos simplificadas vigo de 1
vigo de enemigo del logaritmo de n de n
por logaritmo de ndn al cuadrado de 2 a
la n etcétera y con esto ya podemos
analizar los algoritmos más sencillos
cuando nos topamos con recursividad es
que puede ser un poco más difícil y ahí
vamos a ver otras
para poder llegar al análisis de vigo
por ahora pongamos en práctica todo lo
que hemos visto analizando inserción
sort el algoritmo que vimos en el vídeo
pasado que si no he visto te lo dejo por
acá aquí tengo el código de inserción
sort en java y para empezar a analizarlo
lo que voy a hacer es ver cuántas veces
se ejecuta cada línea según las reglas
escribimos de la anotación de vigo y así
esta primera línea se considera big o de
1 no estoy haciendo nada en particular
es una línea normal pero ya la siguiente
que es este ciclo de acá como recorre la
entrada que es el arreglo y lo hace con
incrementos constantes en este caso de
uno en uno se ejecuta n veces esto sería
big joe de n por lo mismo todo lo que
esté dentro de este bloque de código
también sea ejecutar n veces por lo que
todas las líneas de acá tendrían
pero cuando llegamos a este otro ciclo
interior se va a ejecutar más veces que
las n que toma por el primer ciclo así
que analizado mejor este otro white
tiene una condición aquí que va a
determinar cuándo es que se sale de este
ciclo y recuerden que esto es vivo
así que asumimos que siempre se va a
tardar lo más que pueda eso significa
que nunca va a encontrar la posición en
el sub arreglo antes de llegar al final
siempre va a llegar al final que es el
camino que le va a tomar más pasos para
llegar por lo cual cuando jota sea uno
en la primera iteración del primer ciclo
este otro ciclo acá se va a ejecutar una
vez hasta que llegue a cero al inicio
luego cuando jota sea 2 se ejecuta dos
veces luego cuando jc 3 se ejecuta 3 lo
4 luego 5 luego 6 y así sucesivamente
eso nos diría que esta línea es a
ejecutar primero una vez luego de otras
24 los 5 veces una por cada iteración
del primer ciclo pero
simplificarlo solo tienen que pensar que
también recorre la entrada utilizando
está ahí que se inicializa a través de
jota y lo va haciendo con decrementos
constantes en este caso de uno en uno
por lo tanto también se considera este
ciclo que recorre la entrada y por lo
tanto se ejecuta n veces pero como ya
teníamos en ejecución es por estar
adentro de este otro ciclo tendríamos
que juntarlos sería que esa línea se
ejecuta n veces por cada interacción del
ciclo primero que eso también sería n
veces y ya simplificando esto en el
depor n
nos daría en al cuadrado y como este
ciclo se ejecuta en al cuadrado pues lo
que está adentro también
una vez que hemos salido del ciclo esta
última y nada acá como está dentro de el
primer ciclo se ejecuta también n veces
y ya está sumando todo lo que calculamos
simplificándolo y quedándonos con el
término más significativo nos queda big
o de n al cuadrado que es ya la
complejidad de nuestro algoritmo por
ahora sería todo espero les haya servido
el vídeo platiquen me abajo en los
comentarios si tienen alguna duda o
quieren ver algún tema en especial si
aprendieron algo porfa regalarme un like
compartan con sus amigos y no olviden
suscribirse y darle al botón de la
campanita para que no se pierdan los
siguientes vídeos
[Música]
ah
no no
Посмотреть больше похожих видео
Estructura de Datos - Análisis de Algoritmos, Complejidad
Cómo administrar tu tiempo de manera más efectiva (según las máquinas) - Brian Christian
1. Introducción: Definición de Mecánica de Fluidos
Estructura de programación CONDICIONAL MÚLTIPLE 🔱
Ordenamiento Quicksort (Rápido!) en Java
Vértice de una parábola
5.0 / 5 (0 votes)