Es muy importante saber cómo analizar nuestros algoritmos y para eso utilizamos la anotación de Big O checando cómo están los diferentes ciclos, las líneas de código y demás. Pero, ¿qué pasa cuando nuestro algoritmo es recursivo? Pues en este vídeo precisamente vamos a ver tres técnicas diferentes para poder analizar nuestros algoritmos recursivos.
Soy Chio y bienvenido a ChioCode. Si es tu primera vez por acá, soy profesor en la universidad y desarrollador enfocado en backend, diseño, arquitectura de software y sistemas distribuidos. Y en este canal subo videos sobre esos y muchos otros temas relacionados al software y la programación en general. Así que, si te gusta lo que hago por acá, considera suscribirte.
Muy bien, ya vimos qué es Vigo y cómo hacemos este tipo de análisis en algoritmos que no tienen recursividad. Si no lo has visto, te lo dejo por acá, échale un ojo porque vamos a necesitar varias cosas que... en ese vídeo como quiera vamos a dar un recap rápido y cuando digo rápido es muy rápido porque tenemos muchas muchas cosas que ver la notación vivo nos permite fijar una relación en el peor de los casos sobre cómo va creciendo el tiempo de ejecución de un algoritmo conforme la entrada va incrementando su definición formal dice que una función f pertenece a big out de otra función g cuando existe una constante positiva se tal que a partir de un valor inicial de n F de N no sobrepase a C multiplicando a G de N. Esta definición formal ni siquiera la mencioné en el video anterior porque puede ser un poco confusa y ni siquiera es tan útil en la práctica, pero para uno de los análisis que vamos a utilizar hoy la vamos a ocupar. Lo que sí vimos en el video anterior son diferentes formas de determinar la complejidad VGO de un algoritmo, analizando ¿Cómo están dispuestos los diferentes ciclos que están dentro de las líneas del código?
Esto, claro, siempre y cuando el algoritmo no tenga ninguna llamada recursiva. ¿Y qué hacemos cuando tiene llamadas recursivas? Pues, otro tipo de análisis.
Y aquí les voy a mostrar tres diferentes. El método de sustitución, el método del árbol recursivo y el método maestro. Estos son métodos para resolver recurrencias.
O lo que es lo mismo, es para determinar la complejidad Beagle de... recurrencias y llamamos recurrencias a una ecuación que define una función en términos de esa misma función pero con valores más pequeños o sea es una forma de representar una secuencia recursiva utilizando una fórmula estas recurrencias van muy de la mano con nuestras funciones recursivas porque nos permiten una forma de representar los tiempos de ejecución el cuánto tardan esas funciones de una manera matemática y en realidad no son tan difíciles de crear Por ejemplo, si tomamos el código del clásico ejemplo del factorial, podemos representar el tiempo de esta función con una recurrencia como esta, donde el tiempo que tarda la función para un número n es el tiempo que tarda esa misma función para n-1, más todo lo demás que hacemos en la función, que en este caso es simplemente una suma. Y como ya vimos en el video anterior, esa suma cuando la analizamos es bigou de 1, tiempo constante. Aparte a esta recurrencia le agregamos el caso base para demostrar que cuando n vale 1, entonces el tiempo también es constante.
Para poner... otro ejemplo si aplicamos la misma lógica para el algoritmo de Fibonacci podemos ver que su función de recurrencia tiene esta forma. Chéquense cómo aquí hay dos llamadas recursivas así que lo mismo aparece en la función de recurrencia. Aunque en la práctica hay algunos detalles con estas recurrencias por ejemplo recuerdan el algoritmo que vimos sobre el subarreglo máximo?
Vamos a hacer su función de recurrencia. Esta es la parte principal del algoritmo y si aplicamos la misma lógica para hacer la función de recurrencia checando dónde se hacen las llamadas recursivas, cómo se hacen y qué se hacen, todo lo demás, tenemos que el tiempo es igual a el tiempo que nos tardamos en la primera llamada recursiva con la mitad de la izquierda más el tiempo que nos tardamos en hacer la segunda llamada recursiva con la mitad de la derecha más el tiempo que nos tardamos en hacer todo lo demás. Que en este caso sería dividir el arreglo por la mitad, ejecutar la función para el caso donde el subarreglo máximo pasa por esa división y la función...
max que calcula cuál de esos tres subarreglos es en realidad el más grande y haciendo el análisis normal que ya vimos en el vídeo anterior sobre estas partes ya sabemos que la complejidad de todo lo demás que no sea lo recursivo es bigode n por lo que la función de recurrencia quedaría así noten como en las dos llamadas recursivas hay algo diferente y es que en realidad cuando dividimos el arreglo por la mitad si el tamaño del arreglo no es par nos va a quedar un arreglo un poquito más chiquito que el otro entonces para la primera llamada recursiva hacemos el redondeo hacia abajo y para la segunda llamada recursiva hacemos el redondeo hacia arriba Y estos son los detalles. Normalmente ya cuando estamos en la práctica haciendo análisis sobre este tipo de algoritmos, ignoramos estas condiciones límites, inclusive el caso base lo ignoramos. Esto nos deja con una ecuación mucho más sencilla con la cual podemos trabajar. Noten como aquí convertí big O de n a su definición formal.
Una constante c multiplicando a lo que tenía dentro big O, que en este caso es n. Y ahora sí, utilicemos esta recurrencia del algoritmo del subarreglo máximo. para ver los diferentes métodos que tenemos para solucionarla. Empezando con el método de sustitución. Y aquí una pequeña advertencia, porque para este método utilizamos inducción matemática para demostrar que la solución funciona.
Y si no estás muy acostumbrado a este tipo de procesos o flujos matemáticos, puede ser que el método se te haga muy intimidante. Si es así, dale una oportunidad, no es tan complicado. Y si como quiera se te hace muy muy difícil, espérate a ver el segundo método, que creo yo es mucho más intuitivo.
Muy bien, y entonces sí, ¿cómo funciona el método de sustitución? Son básicamente dos partes. Primero, adivinamos la solución y después utilizamos la inducción matemática para demostrar que esa solución sí es la correcta.
Y acá lo difícil en realidad es adivinar correctamente la solución. Y pongamos por ejemplo el subarreglo máximo. Digamos que yo soy un programador con mucha experiencia y su función de recurrencia ya se me hace conocida. Entonces yo intuyo, adivino y digo que su solución es big O de n por logaritmo de n, que utilizando la definición de big O se escribiría así.
Y ahora para la parte de la inducción matemática, tengo que asumir que esta suposición que yo hice es cierta para todos los números más pequeños que n, que la solución de n por logaritmo de n sí aplica y sí es verdad para todos los números más pequeños. pequeños que n. Estos números más pequeños los voy a llamar m y esto lo utilizo para demostrar lo que yo necesito, que el tiempo de mi función es big O de n por logaritmo de n, o lo que es lo mismo que el tiempo de mi función es menor o igual a una constante c multiplicando a n por logaritmo de n.
Esto otra vez asumiendo que sí aplica para todos los números más pequeños que n. Es la base de la inducción matemática, así que vamos a trabajar ahora con la demostración. Estamos asumiendo que mi suposición es verdad para todos los valores m. Entonces lo que voy a hacer es tomar uno de esos valores m, o sea, un número que sea más pequeño que n, y lo voy a utilizar para mi demostración.
Tomaré entonces el valor de n entre 2 y lo voy a poner en mi suposición de Big O para generar esta desigualdad. Lo cual... me va a servir porque lo que yo voy a utilizar para mi demostración es la función de recurrencia, que es esta de acá.
Y si se fijan hay unos términos que son iguales y aquí es donde viene la parte de la sustitución. En mi función de recurrencia voy a sustituir la parte de la recurrencia con lo que yo asumí que es verdad. Voy a quitar la llamada recursiva t de n entre 2 y voy a poner ahí mi suposición. Que como es una desigualdad, pues ahora toda mi función es una desigualdad.
Y esta parte derecha de la desigualdad la podemos ir simplificando. Y el chiste es que lo hagamos hasta ver si nos sale en realidad lo que nosotros suponemos que es verdad. Entonces simplificamos quitando este 2 de acá que está multiplicando con este 2 de acá que está dividiendo.
Así que ahora lo que tenía es igual a esto otro de acá. Luego por propiedades de los logaritmos puedo dividir ese logaritmo de n entre 2 en dos logaritmos. Logaritmo de n menos logaritmo de 2. Estos logaritmos son base 2 y al final de cuentas un logaritmo base 2 de 2 es 1. Lo escribo por acá y ahora esta suma la puedo reescribir como una simple multiplicación de un término.
Y si se fijan lo que tenemos ahora es c multiplicando a n por logaritmo de n menos otro término. Por lo que como le estamos restando algo a c por n por logaritmo de n, podemos determinar que esta parte es menor o igual a c por n por logaritmo de n. Y esto es justamente lo que quería demostrar.
Si hubiera hecho esta suposición con algún otro valor de big O, no sé, n al cuadrado, me habría salido algo totalmente diferente. Lo que demostraría que mi suposición en un principio era incorrecta. Intenten hacer... esta misma demostración con esta función de recorrencia pero utilicen otro valor de bigo a ver ¿Qué les sale?
Cuéntenme abajo en los comentarios. Pero si se les hizo muy complicado, entonces mejor veamos el segundo método, que creo yo es mucho más sencillito. Es el árbol de recurrencia. Este método funciona dibujando de forma gráfica un árbol que representa las diferentes llamadas recursivas que se hacen dentro del algoritmo. Entonces, empecemos con nuestra función de recurrencia.
Y recordando los pasos de divide y vencerás, primero dividimos nuestro problema en subproblemas, después solucionamos de forma recursiva esos subproblemas. problemas y al final las soluciones que tenemos las juntamos para tener la solución de nuestro problema original. Y el tiempo que nos tardamos en hacer todo esto es justamente lo que tenemos representado dentro de nuestra función de recurrencia. Es lo que nos tardamos en esos dos subproblemas más pequeños más lo que nos tardamos en hacer todo lo demás.
tanto la división como la combinación de las soluciones. Y esto lo podemos representar con un arbolito. El tiempo que nos tardamos en ejecutar la función es el tiempo que nos tardamos en hacer la separación y la combinación de nuestras soluciones, más lo que sea que nos tardemos en esos dos subproblemas.
Acá ya empezamos a formar este árbol. Por lo pronto tenemos solamente dos nodos hijos, pero para saber cuánto tiempo nos vamos a tardar en esos dos nodos, podemos expandir. nuestro árbol otro nivel en este otro nivel cada uno de los subproblemas que vayan a salir son todavía más pequeños nuestro n entre 2 tenemos que dividirlo otra vez entre 2 lo que nos daría n entre 4 y luego para poder combinar estos nuevos subproblemas también me voy a tardar cierto tiempo que va a ser un poquito menos que antes si sustituimos todo dentro de mi función de recurrencia me voy a dar cuenta que para la parte de la combinación me voy a tardar n entre 2. Y este ya sería el árbol con el nuevo nivel.
Y esto puede continuar hasta que lleguemos al caso base. ¿Cuál sería el caso base? Pues cuando n valga 1. Y la idea es que si sumamos todos los nodos de mi árbol, voy a tener al final la complejidad de mi algoritmo.
Bueno, ¿y entonces voy a tener que dibujar todo mi arbolito? No. La idea es que al dibujar unos cuantos niveles nos vayamos dando cuenta de ciertos patrones donde podamos extraer de ahí valores para llegar al final a mi resultado. Por ejemplo, lo que hacemos siempre es sacar el total de cada uno de los niveles. Al final de cuenta, en este segundo nivel tengo que sumar n entre 2 más n entre 2. Tengo que sumar los dos nodos.
Y me doy cuenta ahí que el total de ese renglón, de ese nivel, es n. Si hago lo mismo con el tercero, sale lo mismo, N. Si saco este total de todos los niveles y lo sumo todos los totales, voy a tener mi resultado. Y aquí es donde detectamos el patrón.
Si se fijan, en todos los niveles en este ejemplo, el resultado es N. No siempre es así, esto simplifica mucho nuestro análisis, pero en otros casos puede ser que sea una progresión geométrica. De cualquier forma, lo que tengo que hacer es sumar todos esos totales. En este ejemplo, sé que todos los totales es N. n.
Entonces solamente tengo que saber cuántas n hay, cuántos niveles hay en mi arbolito. ¿Y cuántos niveles hay en nuestro árbol? Bueno, pues eso depende de cómo se vaya dividiendo nuestro problema original.
Siempre que el problema se divida entre un número para generar los nuevos subproblemas, el tamaño de mi árbol recursivo va a ser igual al logaritmo base, el número por el cual se dividió, de n, que en este caso sería logaritmo base 2. Y con esto lo único que nos queda es multiplicar n, que es el total de cada uno de los niveles, por logaritmo de n, que es el tamaño o el número de niveles que tenemos dentro de nuestro árbol. Y así de simple, tenemos que sacar cuántos niveles tiene nuestro árbol y tenemos que sacar cuál es el total de tiempo que tarda cada uno de los niveles. Aunque este método tiene algunos problemas con ciertos algoritmos que no van dividiendo en cada llamada recursiva. Por ejemplo...
Fibonacci o factorial que van restando a n en cada llamada recursiva. Como no es una división, estas fórmulas no funcionan bien para determinar el árbol de recurrencia. Para ese tipo de algoritmos es mejor utilizar el método de sustitución. Lo que sí es que este método del árbol recursivo es tan bueno para resolver algunas recurrencias que de él sale el siguiente método, el método maestro, el cual es simplemente una serie de reglas y funciones en donde si tu función de recurrencia tiene esta forma de acá, donde A tiene que ser mayor o igual a 1 y B tiene que ser mayor que 1, entonces tu complejidad cae en uno de estos tres casos.
¿Cómo lo hacemos entonces? Bueno, tomamos nuestra función de recurrencia e identificamos los diferentes términos que vamos a necesitar. A, B y F de N.
Primero tomamos el valor de B y A y calculamos esta parte de acá, para luego checar en cuál de los tres casos cae. Para que mi función f de n sea igual a bigou de n elevado a la c. Y aquí lo importante de ver es qué valor tiene que ser c.
Para eso calculamos la parte de el logaritmo base b de a. Si c es exactamente igual para que esto se cumpla, entonces cae en el segundo caso. Si al contrario necesitas que c sea más pequeño, entonces cae en el primer caso.
Y si necesitas que sea más grande, cae en el tercer caso. Y dependiendo de en cuál caso caiga... reemplazamos los valores que extrajimos de nuestra función de recurrencia con los que están mostrados por acá y con eso ya determinamos cuál es nuestra complejidad. Muy importante que la función de recurrencia tiene que tener exactamente esa forma.
No puede ser, por ejemplo, la función del factorial, donde se están restando valores cada vez que se hace la llamada recursiva. Tiene que estar a fuerza dividiendo. Y ya está. Esos serían tres métodos para hacer el análisis BigO. En nuestros algoritmos recursivos.
Traté de hacer este video lo más cortito posible. Pero podemos ahondar muchísimo más. En cada uno de estos métodos. Cuéntenme abajo en los comentarios.
Si quieren que profundicemos más. En cada uno de los métodos. O si tienen preguntas o dudas.
También platíquenme por ahí abajo. Voy a dejar en la descripción del video. Varias referencias con material.
Para que puedan profundizar más. En todos los métodos diferentes. Pero si les ayudó el video. Porfa. regalenme un like, compartan con sus amigos y no olviden suscribirse y darle al botón de la campanita para que no se pierdan el siguiente vídeo.
Bye!