Muy bueno el video. Si a alguien le interesa profundizar porque se obtiene un orden logarítmico en algoritmos como el de búsqueda binario que se muestra al principio del video, es por que lo que determina el tiempo de ejecución es la cantidad de divisiones que tendremos que realizar. Partimos de n y realizamos tantas divisiones como sea necesario hasta llegar a un array de largo 1, a esto lo podemos escribir como n/2/2/2/.....etc, no sabemos el total de divisiones por lo que escribimos lo mismo pero en términos de n/2^k = 1, simplificamos y obtenemos n=2^k. El valor de k se obtiene calculando el logaritmo en base 2 de n, esto es log(n) = k. De esta manera obtenemos k que como mencioné es el número de iteraciones que realizara el bucle, por lo tanto el orden del algoritmo.
Gran, gran explicación Marcos, muchas gracias. La verdad, pocas veces veo videos de youtube de más de 15 minutos, casi siempre por que son mucho bla bla bla y poco contenido, y ... porque dan flojera. Pero tu video se me fué rápido por lo preciso y bien explicado, es por éso mi agradecimiento. Saludos!
siempre me complicaba el ordenamiento al estudiar, gracias a este video lo tengo mucho mas claro, asi que muchas gracias, de verdad que me ayudo mucho.
El ejemplo de Fibonacci recursivo está mal, deberia ser: return f(n -1) + f(n-2). El arbol decreamenta en longitud en la funcion de f(n-2). Por el tema de la constante y tomar el dominante sigue quedando de O(2^N) ?
En realidad no era el algoritmo de Fibonacci, se equivocó al decir que lo era, el ejemplo en sí es el que viene en un libro, de hecho es exactamente el temario del libro de “Cracking the coding interview”.
Hola marco me interesa aprender algoritmos ya que independientemente del lenguaje siempre es bueno saberlo para resolver problemas que son muy abatractos se resolver, recomiendas algun libro, o lugar para empezar a estudiar algoritmos? Gracias de antemano
Por que llega un punto en que al crecer mucho N, y va a superar a N ^100, un ejemplo mas claro hubiera sido N^10; (constante) ^ N va a crecer mucho mas rápido que N ^ (constante), ya que el grado del exponente es el que aumenta.
Amigo, tengo un problema, tengo un ejercicio parecido al ejemplo que diste de recursividad, solamente que el mio devuelve un solo resultado y no se va incrementando de a dos como en el tuyo... En mi caso sería : Static int pot2(int N) { If(n==0){ Return 1; } Return 2*pot2(n-1); }
Me animo a decir y basados en lo que se menciona en 8:00, la complejidad radica en el valor de N y no tanto en las constantes. El hecho de que regrese el doble del valor al final, no modifica su complejidad.
Yo pienso que es O(N). c1 = va a ser el tiempo que tomara el caso mas facil, o sea pot2(0) c2 = va a ser el tiempo en hacer la operacion 2 * (numero que devuelve la funcion), no considero el tiempo de la funcion recursiva. t(n-1) : va aser el tiempo que retornara la funcion recursiva un valor. ahora la funcion recursiva general es: t(n) = t(n-1) +c2,; ----> c1 no lo considero,por que es el caso mas facil, el big-o es para el peor de los casos. t(n) = t(n-2) +c2 + c2 t(n) = t(n-3) +c2+c2+c2 la funcion general es : t(n-k) + k*c2 ahora para que sea el peor caso debe ser k = n - 1 para que la funcion sea la mas larga posible. t( 1 ) + (n-1)*c2 , y en el video el o dominate es O(N). Todo esto creo que esta bien, pero no lo aseguro al 100%. Corrijanme si es necesario. Edit: ya lo resolvi si es O(n) ya que la funcion solo se llama asi misma una sola vez, en la de fibonacci fue por que se llamaba dos veces, y asi era 2 a la N,puede parecer contraintuituvo pero hay varios algoritmos recursivos O(n) como el tuyo
Las funciones recursivas son recomendadas cuando tienen operaciones básicas y tienen bien definida la condición de salida, ya que de lo contrario se vuelven anidadas y podrían ofrecer un rendimiento muy lento
La notación Big O es fundamental para un programador ¿ya conocías el término? ¿sabes la eficiencia de tus algoritmos?
Muy bueno el video. Si a alguien le interesa profundizar porque se obtiene un orden logarítmico en algoritmos como el de búsqueda binario que se muestra al principio del video, es por que lo que determina el tiempo de ejecución es la cantidad de divisiones que tendremos que realizar. Partimos de n y realizamos tantas divisiones como sea necesario hasta llegar a un array de largo 1, a esto lo podemos escribir como n/2/2/2/.....etc, no sabemos el total de divisiones por lo que escribimos lo mismo pero en términos de n/2^k = 1, simplificamos y obtenemos n=2^k. El valor de k se obtiene calculando el logaritmo en base 2 de n, esto es log(n) = k. De esta manera obtenemos k que como mencioné es el número de iteraciones que realizara el bucle, por lo tanto el orden del algoritmo.
Justo estaba leyendo el libro "Cracking the code interview" y me topo con esto. Me ayudó mucho, Gracias.
Yo también estoy leyendo el libro, primera vez que escucho el termino.
SeNores, yo tambien estoy leyendo el libro. Y el ejemplo del avion del principio aparece en la seccion Big O del libro :P
¿Caballeros, aquí es el club de los que estamos en esa sección del libro en diferentes momentos de la historia del tiempo del universo?
😄Igualmente llegue aqui buscando entender mas el ejemplo del libro CCI.
Gran, gran explicación Marcos, muchas gracias. La verdad, pocas veces veo videos de youtube de más de 15 minutos, casi siempre por que son mucho bla bla bla y poco contenido, y ... porque dan flojera. Pero tu video se me fué rápido por lo preciso y bien explicado, es por éso mi agradecimiento. Saludos!
Gracias Arturo!!! Me da gusto que hayas encontrado el video útil 😊😊
Los ejemplos del final son muy buenos, de los mejores que he visto.
Gracias por tu comentario Edgar!
Excelente video, me quedó muy claro para ser un primer acercamiento al tema, lo seguiré estudiando. gracias!
buenisimo!!!!!! queda mucho mas claro en el video que leer el libro
Actualmente, estoy aprendiendo este concepto de Big-O. Es un poco dificil de entender, pero gracias a videos como este, uno se da mejor idea!
Qué bueno que te sirve el vídeo, no es un concepto fácil de entender y requiere un poco de práctica por lo abstracto que es
Muy buena explicacion, se ve que tomaste tiempo para armarla, te agradezco.
siempre me complicaba el ordenamiento al estudiar, gracias a este video lo tengo mucho mas claro, asi que muchas gracias, de verdad que me ayudo mucho.
Excelente vídeo, había visto esto en la universidad, en Algoritmos 2. Muy bien explicado, gracias!
es sùper útil para ser un buen programador
me estan dando esto, en programación 1 (una materia del año 1 ) D:
Es un video muy completo, muchas gracias
Buen ejemplo amigo, te ganaste un buen pulgar arriba y +suscriptor
Muy buen video, el mejor que he visto sobre el tema, sobretodo por los ejemplos del final, muchas gracias.
creo que for que apareció en el minuto 21:50 realmente es logarítmica ya que hice varias pruebas y no se ejecuta la mitad de veces que si fuera solo x
muy claro, gracias x explicar
Excelentes explicación muchas gracias
El ejemplo de Fibonacci recursivo está mal, deberia ser: return f(n -1) + f(n-2). El arbol decreamenta en longitud en la funcion de f(n-2). Por el tema de la constante y tomar el dominante sigue quedando de O(2^N) ?
Iba a comentar justamente lo mismo. Ahora no se si todo el . ideo esta mal ._.
En realidad no era el algoritmo de Fibonacci, se equivocó al decir que lo era, el ejemplo en sí es el que viene en un libro, de hecho es exactamente el temario del libro de “Cracking the coding interview”.
@@victorespinoza8185 Cierto, también me di cuenta de eso.
Hola marco me interesa aprender algoritmos ya que independientemente del lenguaje siempre es bueno saberlo para resolver problemas que son muy abatractos se resolver, recomiendas algun libro, o lugar para empezar a estudiar algoritmos? Gracias de antemano
Yo he hecho todo esto y no sabia que era BigO jajaja. Hasta ahora que estoy tomando un curso de algoritmia.
Muchas gracias! Muy bueno e instructivo!
Quisiera saber que tan complejo son O(a+b) y O(a*n) que no se muestran en la grafica 6:23
Ese ejemplo lo vi en el libro Cracking the code interview
¡Magnifica explicación!
hola, de que libro puedo sacar informacion sobre esta notacion?
se vasa en el libro cracking the coding interview
Muchas gracias y buen vídeo
Excelente explicación!
Muchas gracias!
En el ejemplo del array creo que es de O(N) porque con los FOR anidados solo se recurre una vez los elementos del array.
Eres un crack!!!!
porque se resume a 2^n y no a 10^n? min 10:00
Por que llega un punto en que al crecer mucho N, y va a superar a N ^100, un ejemplo mas claro hubiera sido N^10; (constante) ^ N va a crecer mucho mas rápido que N ^ (constante), ya que el grado del exponente es el que aumenta.
Gracias de mucha ayuda!
Amigo, tengo un problema, tengo un ejercicio parecido al ejemplo que diste de recursividad, solamente que el mio devuelve un solo resultado y no se va incrementando de a dos como en el tuyo... En mi caso sería :
Static int pot2(int N) {
If(n==0){
Return 1;
}
Return 2*pot2(n-1);
}
Me animo a decir y basados en lo que se menciona en 8:00, la complejidad radica en el valor de N y no tanto en las constantes. El hecho de que regrese el doble del valor al final, no modifica su complejidad.
Yo pienso que es O(N).
c1 = va a ser el tiempo que tomara el caso mas facil, o sea pot2(0)
c2 = va a ser el tiempo en hacer la operacion 2 * (numero que devuelve la funcion), no considero el tiempo de la funcion recursiva.
t(n-1) : va aser el tiempo que retornara la funcion recursiva un valor.
ahora la funcion recursiva general es:
t(n) = t(n-1) +c2,; ----> c1 no lo considero,por que es el caso mas facil, el big-o es para el peor de los casos.
t(n) = t(n-2) +c2 + c2
t(n) = t(n-3) +c2+c2+c2
la funcion general es : t(n-k) + k*c2
ahora para que sea el peor caso debe ser k = n - 1 para que la funcion sea la mas larga posible.
t( 1 ) + (n-1)*c2 , y en el video el o dominate es O(N).
Todo esto creo que esta bien, pero no lo aseguro al 100%. Corrijanme si es necesario.
Edit: ya lo resolvi si es O(n) ya que la funcion solo se llama asi misma una sola vez, en la de fibonacci fue por que se llamaba dos veces, y asi era 2 a la N,puede parecer contraintuituvo pero hay varios algoritmos recursivos O(n) como el tuyo
hola y que algoritmo me daria para decir que es O(log n)??
La búsqueda binaria que explica al minuto 12:30 es O(log n)
muy buen video
Como se expresa en complejidad temporal O(A+B)?... Logaritmica???...
Esta bien el video para darse una idea, pero creo que aún hay partes que no se entienden tan bien.
qué parte del video no entendiste bien Mario? para ver cómo mejoro esa parte
@@vidamrr minuto 15:40
una pregunta, entonces usar funciones recursivas nunca es óptimo no?
Las funciones recursivas son recomendadas cuando tienen operaciones básicas y tienen bien definida la condición de salida, ya que de lo contrario se vuelven anidadas y podrían ofrecer un rendimiento muy lento
como que me va a tocar repetir el video varias veces jajaja
gracias
creo que estan mal los for no son O(n), porque la sumatoria de los primeros n es (n^2)
O(raiz de N ) = O(N^(1/2)) por tanto es uns funcion exponencial
Vine a ver la explicación de la Big O? O vine a ver comerciales???? MIl millones de anuncios cada 2 segundos!!!!! es demasiado!!!
El audio está horrible
no entendi nada XD
Salen propagandas cada 20 segundos.