Notación Big O | Análisis de algoritmos de forma sencilla

Chio Code
9 Dec 202012:33

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

00:00

🕵️‍♂️ 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.

05:01

🔍 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.

10:04

🛠 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

La eficiencia en el contexto del video se refiere a la capacidad de los programas para realizar tareas de manera rápida y con el menor uso de recursos posible. Es crucial para arquitectos y programadores, ya que permite prever y garantizar el rendimiento adecuado de un sistema. En el video, se discute cómo la eficiencia es fundamental para entender cuánto 'pesar' puede soportar un algoritmo, es decir, cuánta carga de trabajo puede manejar sin problemas.

💡Complejidad de un algoritmo

La complejidad de un algoritmo es un concepto central en la informática que mide el rendimiento y la eficiencia de un programa. Se describe en términos de la cantidad de recursos (tiempo y espacio) que necesita para completar una tarea. En el video, se explica que la complejidad es esencial para determinar cuánto tiempo, memoria o servidores se necesitarán para ejecutar un programa.

💡Anotación de Vigo

La anotación de Vigo, también conocida como notación asintótica, es una forma de describir la complejidad de un algoritmo de manera abstracta y general. Se utiliza para comparar el rendimiento de diferentes algoritmos sin tener en cuenta factores específicos del hardware o la implementación. En el video, se destaca cómo esta anotación permite analizar y comparar la eficiencia de algoritmos a través de su crecimiento asintótico.

💡Tiempo de ejecución

El tiempo de ejecución es la cantidad de tiempo que un programa o algoritmo toma para completar una tarea. Es un indicador clave de la eficiencia, y en el video se menciona que medir el tiempo de ejecución es una forma de evaluar la eficiencia de un algoritmo, aunque también se señala que este método es simplista y no siempre representa la complejidad real.

💡Constante (V-1)

En la anotación de Vigo, 'constante' (denotado comúnmente como V-1) se refiere a un algoritmo cuya complejidad no varía con el tamaño de la entrada. Esto significa que el tiempo de ejecución es el mismo, independientemente de la cantidad de datos que se procesen. En el video, se da como ejemplo que llevar libros en el carro a una distancia fija tiene un tiempo constante, sin importar cuántos libros se lleven.

💡Lineal (V-n)

La complejidad lineal (V-n) indica que el tiempo de ejecución de un algoritmo aumenta en proporción directa con el tamaño de la entrada. Esto se ve en el video con el ejemplo de correr libros a casa, donde cada libro requiere un viaje adicional, lo que hace que el tiempo total crezca linealmente con el número de libros.

💡Ciclos anidados

Los ciclos anidados son bucles dentro de bucles y son comunes en la programación. Su complejidad varía según el número de bucles y cómo se ejecutan. En el video, se menciona que la complejidad de un algoritmo con ciclos anidados puede ser cuadrática (V-n^2) si los bucles están anidando de manera que la cantidad de iteraciones del segundo depende del tamaño de la entrada del primero.

💡Peor caso

El peor caso en la anotación de Vigo se refiere al escenario en el que un algoritmo toma el mayor tiempo posible para completar una tarea. Es importante para los desarrolladores ya que les permite diseñar sistemas que sean robustos y eficientes incluso en condiciones adversas. En el video, se enfatiza que la anotación de Vigo, particularmente la notación de peor caso, es útil para entender el rendimiento máximo requerido por un algoritmo.

💡Logaritmo (V-log n)

La complejidad logarítmica (V-log n) se refiere a un algoritmo cuyo tiempo de ejecución crece logarítmicamente con el tamaño de la entrada. Esto es significativamente más eficiente que la complejidad lineal o cuadrática, especialmente para grandes conjuntos de datos. En el video, se compara con la complejidad cuadrática para ilustrar la diferencia en la eficiencia de un algoritmo.

💡Insertion Sort

Insertion Sort es un algoritmo de ordenamiento que se menciona en el video para ejemplificar cómo se calcula la complejidad asintótica. Funciona moviendo elementos de un arreglo de tal manera que cada vez que se inserta un nuevo elemento, se compara con los ya ordenados para encontrar su lugar correcto. El análisis del video muestra que su complejidad es cuadrática (V-n^2) debido a la naturaleza de sus ciclos anidados.

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

play00:00

sabemos que es muy importante conocer

play00:01

qué tan eficientes son nuestros

play00:03

programas es lo equivalente a que un

play00:05

arquitecto conozca cuánto peso aguanta

play00:07

un edificio o que un panadero sepa

play00:10

cuántas rosquillas puede hacer en una

play00:12

hora nuestros clientes seguramente nos

play00:14

van a preguntar ese tipo de cosas oye

play00:16

cuando te vas a tardar en procesar todos

play00:19

los documentos cuántas transacciones por

play00:22

segundo aguanta tu aplicación cuántos

play00:24

usuarios puedes manejar qué tanta

play00:26

memoria ocupa cuántos servidores voy a

play00:29

necesitar para aguantar este tráfico y

play00:31

para que nosotros nos demos cuenta cómo

play00:33

se comporta un algoritmo no tenemos por

play00:35

qué siempre ejecutarlos para ver el

play00:37

resultado muchas veces podemos

play00:39

analizarlos y determinar su complejidad

play00:42

utilizando la anotación de vigo o en

play00:45

este vídeo justamente vamos a ver de qué

play00:47

se trata y cómo podemos utilizarlo para

play00:49

analizar nuestros algoritmos soy yo y

play00:52

bienvenido archivo code

play00:54

[Música]

play00:57

bueno

play01:00

para empezar hay que diferenciar qué es

play01:02

lo que podemos analizar y por ende ver

play01:04

qué tan bueno es un algoritmo y podemos

play01:07

hacerlo desde dos perspectivas la

play01:09

primera es el uso de la memoria y la

play01:12

segunda la velocidad qué tan rápido es

play01:15

por hoy vamos a enfocarnos en la

play01:17

velocidad y cómo es que puedo medirla

play01:19

pues podemos simplemente ejecutar

play01:21

nuestro programa contar cuántos segundos

play01:23

se tarda y ya está el detalle es que no

play01:26

es tan sencillo recuerdan que un

play01:28

algoritmo es una secuencia de pasos que

play01:30

toman una entrada y generan una salida

play01:32

bueno pues qué tal si la segunda vez que

play01:35

estoy ejecutando mi programa para medir

play01:37

el tiempo la entrada es el doble de

play01:40

grande entonces se va a tardar el doble

play01:43

de tiempo no la verdad es que no

play01:45

dependiendo del algoritmo el tiempo de

play01:48

ejecución escala diferente con la

play01:50

entrada y esto es más fácil de explicar

play01:52

con un ejemplo imagínate que quiero

play01:54

llevarle unos libros a mi amigo es tema

play01:56

que vive aquí a una cuadra de mi casa y

play01:58

tengo dos métodos para hacerlo el

play02:00

primero es tomar los libros que quieran

play02:03

ponerlos en mi carro y manejar hasta

play02:05

allá

play02:06

no importa cuántos libros quiera

play02:08

llevarles siempre me tardo lo mismo

play02:09

digamos 5 minutos quiero llevar un libro

play02:12

cinco minutos dos libros cinco minutos

play02:15

veinte libros cinco minutos sin importar

play02:18

la entrada en este caso el número de

play02:20

libros el tiempo que me tardo no varía

play02:23

es constante y el segundo método que

play02:25

puedo usar es tomar el libro y correr

play02:27

hacia su casa y con eso me tardo más o

play02:30

menos tres minutos sin tener que dar

play02:32

todas las vueltas en el carro pero

play02:34

solamente puedo llevar un libro a la vez

play02:37

así que si quiero llevar dos tendré que

play02:39

dar dos vueltas y ahora me tardaría seis

play02:41

minutos así que vivar tres son nueve

play02:44

minutos y así va escalando el tiempo que

play02:47

me tardé dependiendo de cuántos libros

play02:50

quiera llevar o dependo de mi entrada en

play02:53

este segundo método del tiempo crece de

play02:55

forma lineal y de la misma manera puede

play02:58

idear otros métodos para mandarle libros

play03:00

y cada uno puede crecer de manera

play03:02

diferente y para poder clasificar todas

play03:05

estas diferentes formas en que crecen

play03:07

los algoritmos dependiendo de la entrada

play03:09

usamos la notación asintótica

play03:13

notaciones sintética no ibas a hablar de

play03:16

vigo sí y es que vigo es una anotación

play03:19

es sintética verás que estas gráficas

play03:22

que muestran cuánto tiempo se tarda un

play03:24

programa en ejecutarse con base a la

play03:27

entrada en la vida real no son tan

play03:30

bonitas hay muchas cosas que afectan la

play03:32

ejecución de un programa ya en una

play03:34

computadora y aunque sea el mismo

play03:37

programa con la misma entrada cuando

play03:39

ejecutas dos o más veces nunca va a ser

play03:42

exactamente igual y estas funciones

play03:44

terminan siendo mucho más complejas así

play03:47

que lo que nos permite la anotación

play03:49

asintótica es poder simplificar estas

play03:52

funciones que representan la tasa de

play03:54

crecimiento de un algoritmo es como si

play03:57

tomáramos un número con decimales y lo

play03:58

redondeamos y así como redondear el

play04:01

número podemos hacerlo hacia arriba o

play04:02

hacia abajo también hay diferentes

play04:04

notaciones asintóticas que podemos

play04:06

utilizar dependiendo de qué es lo que

play04:09

nos interesa si algún límite superior o

play04:11

un límite inferior o los dos

play04:13

ok pero nosotros como desarrolladores lo

play04:15

que más nos interesa y lo que más

play04:17

terminamos usando es el límite superior

play04:20

la anotación de vieja o por qué porque

play04:23

es el límite representa el

play04:25

comportamiento en el peor de los casos y

play04:27

eso normalmente es lo que más nos

play04:29

interesa no es lo mismo que te diga que

play04:31

esta silla soporta más de 50 kilos que

play04:35

tantos más 80 100 200 para sentar un

play04:39

elefante aquí me es más útil conocer qué

play04:41

máximo llega a 150 y ya en base a eso

play04:45

saber cómo poder manejar esta silla o mi

play04:49

algoritmo y recuerden que con esta

play04:51

anotación del big joe estamos tratando

play04:53

de identificar cómo se comportan nuestro

play04:56

algoritmo dependiendo de la entrada así

play04:59

podemos clasificar nuestros programas

play05:00

con diferentes complejidades vigo de uno

play05:03

para definir qué es constante que no

play05:06

varía dependiendo de la entrada vigo de

play05:08

n donde n normalmente representa la

play05:11

entrada y eso significa que está

play05:12

creciendo de manera lineal vigo de n al

play05:15

cuadrado de logaritmo de n de en el

play05:18

logaritmo de n 2 a la n etcétera esto lo

play05:22

que nos dice es que si mi algoritmo es

play05:23

en al cuadrado entre más

play05:26

a la entrada peor se va a comportar y si

play05:29

esa misma entrada la pongo en un

play05:31

algoritmo que sea solamente logaritmo de

play05:33

n se va a comportar muchísimo mejor que

play05:36

mi solución en al cuadrado y entonces

play05:39

cómo podemos analizar nuestro código

play05:40

para determinar cuál es su complejidad

play05:42

bueno cualquier función o línea de

play05:45

código se considera vigo de uno o tiempo

play05:47

constante siempre y cuando no sea un

play05:50

ciclo no tenga recursos o no sea una

play05:54

llamada a una función que a su vez no

play05:57

sea de tiempo constante si es el tiempo

play05:58

constante pues sigue siendo tiempo

play06:00

constante ahora yéndonos a los ciclos se

play06:03

considera vivo de n o tiempo lineal

play06:06

cuando la variable del ciclo va

play06:08

incrementando o incrementando por un

play06:10

número constante o sea que vaya subiendo

play06:12

de uno en uno o de dos en dos o de tres

play06:15

en tres

play06:16

etcétera y siempre y cuando este ciclo

play06:19

vaya y tirando en base a la entrada que

play06:22

vaya recorriendo los números que

play06:23

nosotros le pasamos o vaya recorriendo

play06:25

los caracteres del string o que vaya

play06:27

haciendo algo con la entrada si ese

play06:30

ciclo

play06:31

tres veces y siempre y teherán tres

play06:33

veces independientemente de la entrada

play06:36

que le pusimos se sigue considerando

play06:38

tiempo constante vigo out de uno y

play06:41

cuando tenemos ciclos anidados la

play06:43

complejidad depende de cuántas veces se

play06:45

ejecuta el ciclo que está más adentro

play06:47

llegando a bigote en al cuadrado si son

play06:51

dos ciclos o si son tres ciclos n al

play06:54

cubo en la cuatro en las cinco depende

play06:57

de cuántos ciclos alineados tengamos

play06:59

dentro y si todos esos ciclos también y

play07:03

teherán basándose en la entrada en la

play07:06

entrada o en variables que a su vez

play07:08

están basándose en la entrada ahora si

play07:10

la variable del ciclo en lugar de estar

play07:12

incrementando por un número constante va

play07:15

multiplicándose o dividiéndose esta

play07:18

complejidad se convierte en logaritmo de

play07:20

n iia así de plano va incrementándose de

play07:22

forma exponencial entonces se considera

play07:25

logaritmo del logaritmo de n bueno y qué

play07:27

pasa si tenemos condicionales adentro de

play07:29

los ciclos y ahí recuerden que estamos

play07:31

calculando vic o que es el

play07:33

comportamiento en el peor de los casos

play07:35

así que

play07:36

cuando nos topamos con ese if tomamos la

play07:39

decisión de entrar o de saltarnos los

play07:42

dependiendo de cuál nos vaya a ser

play07:44

ejecutar el mayor número de líneas la

play07:47

decisión que nos lleve por la peor ruta

play07:49

que nos haga tomar el peor caso y una

play07:53

vez que hayamos ya calculado esto de

play07:55

diferentes secciones con diferentes y

play07:57

llamadas al sistema etcétera lo que

play07:59

hacemos es sumar todas esas

play08:01

complejidades y simplificarlo recuerden

play08:04

que la anotación es sintética se trata

play08:06

de simplificar así que de la suma que

play08:08

nos haya quedado vamos a tomar solamente

play08:11

el término más significativo o sea el

play08:14

cachito que sea el más grande quitando

play08:18

cualquier constante un número que esté

play08:19

multiplicando al valor de n para que así

play08:22

nos quede alguna complejidad de las que

play08:24

ya conocemos simplificadas vigo de 1

play08:26

vigo de enemigo del logaritmo de n de n

play08:29

por logaritmo de ndn al cuadrado de 2 a

play08:32

la n etcétera y con esto ya podemos

play08:34

analizar los algoritmos más sencillos

play08:36

cuando nos topamos con recursividad es

play08:39

que puede ser un poco más difícil y ahí

play08:42

vamos a ver otras

play08:43

para poder llegar al análisis de vigo

play08:46

por ahora pongamos en práctica todo lo

play08:48

que hemos visto analizando inserción

play08:50

sort el algoritmo que vimos en el vídeo

play08:52

pasado que si no he visto te lo dejo por

play08:54

acá aquí tengo el código de inserción

play08:56

sort en java y para empezar a analizarlo

play08:58

lo que voy a hacer es ver cuántas veces

play09:00

se ejecuta cada línea según las reglas

play09:03

escribimos de la anotación de vigo y así

play09:05

esta primera línea se considera big o de

play09:09

1 no estoy haciendo nada en particular

play09:12

es una línea normal pero ya la siguiente

play09:14

que es este ciclo de acá como recorre la

play09:18

entrada que es el arreglo y lo hace con

play09:20

incrementos constantes en este caso de

play09:23

uno en uno se ejecuta n veces esto sería

play09:27

big joe de n por lo mismo todo lo que

play09:31

esté dentro de este bloque de código

play09:33

también sea ejecutar n veces por lo que

play09:37

todas las líneas de acá tendrían

play09:40

pero cuando llegamos a este otro ciclo

play09:43

interior se va a ejecutar más veces que

play09:45

las n que toma por el primer ciclo así

play09:49

que analizado mejor este otro white

play09:51

tiene una condición aquí que va a

play09:54

determinar cuándo es que se sale de este

play09:57

ciclo y recuerden que esto es vivo

play10:00

así que asumimos que siempre se va a

play10:03

tardar lo más que pueda eso significa

play10:06

que nunca va a encontrar la posición en

play10:08

el sub arreglo antes de llegar al final

play10:10

siempre va a llegar al final que es el

play10:13

camino que le va a tomar más pasos para

play10:16

llegar por lo cual cuando jota sea uno

play10:20

en la primera iteración del primer ciclo

play10:22

este otro ciclo acá se va a ejecutar una

play10:26

vez hasta que llegue a cero al inicio

play10:28

luego cuando jota sea 2 se ejecuta dos

play10:31

veces luego cuando jc 3 se ejecuta 3 lo

play10:34

4 luego 5 luego 6 y así sucesivamente

play10:37

eso nos diría que esta línea es a

play10:39

ejecutar primero una vez luego de otras

play10:41

24 los 5 veces una por cada iteración

play10:45

del primer ciclo pero

play10:47

simplificarlo solo tienen que pensar que

play10:50

también recorre la entrada utilizando

play10:52

está ahí que se inicializa a través de

play10:54

jota y lo va haciendo con decrementos

play10:57

constantes en este caso de uno en uno

play11:01

por lo tanto también se considera este

play11:03

ciclo que recorre la entrada y por lo

play11:06

tanto se ejecuta n veces pero como ya

play11:09

teníamos en ejecución es por estar

play11:11

adentro de este otro ciclo tendríamos

play11:13

que juntarlos sería que esa línea se

play11:16

ejecuta n veces por cada interacción del

play11:20

ciclo primero que eso también sería n

play11:24

veces y ya simplificando esto en el

play11:26

depor n

play11:30

nos daría en al cuadrado y como este

play11:33

ciclo se ejecuta en al cuadrado pues lo

play11:35

que está adentro también

play11:39

una vez que hemos salido del ciclo esta

play11:42

última y nada acá como está dentro de el

play11:44

primer ciclo se ejecuta también n veces

play11:48

y ya está sumando todo lo que calculamos

play11:51

simplificándolo y quedándonos con el

play11:53

término más significativo nos queda big

play11:57

o de n al cuadrado que es ya la

play12:00

complejidad de nuestro algoritmo por

play12:04

ahora sería todo espero les haya servido

play12:05

el vídeo platiquen me abajo en los

play12:07

comentarios si tienen alguna duda o

play12:09

quieren ver algún tema en especial si

play12:11

aprendieron algo porfa regalarme un like

play12:14

compartan con sus amigos y no olviden

play12:16

suscribirse y darle al botón de la

play12:18

campanita para que no se pierdan los

play12:19

siguientes vídeos

play12:23

[Música]

play12:24

ah

play12:26

no no

Rate This

5.0 / 5 (0 votes)

関連タグ
Análisis de algoritmosNotación BIG OEficiencia computacionalProgramaciónDesarrollo de softwareOptimización de códigoTiempo de ejecuciónProgramación eficienteCómputo asintóticoOptimización de algoritmos
英語で要約が必要ですか?