Duda sobre Tamaño de un Algoritmo

E

ErCordobes #1 Nov '14

Hola, muy buenas a todos. Llevo varios días dándole vueltas a ésto pero no consigo avanzar demasiado.

Veréis, tengo que dar una definición recursiva para el llamado "Triangulo de Pascal" que viene a ser este:

El método/función me debe calcular el número correspondiente dada una fila y columna en el nombrado triángulo. Por ejemplo para la fila(siendo n) 4 y la columna(siendo m) 1 debe de devolver 4. Aclarar, que la primera fila y columna serían 0,0. El código y la definición no hay problema, pero debo de hallar también el tamaño y complejidad del algoritmo y no consigo ver del todo el tamaño.

La definición recursiva es esta (o eso creo):

El código es este:

Integer pascal(Integer n, Integer m) {
	Integer res;
	if (n == m || m == 0) {
		res = 1;
	} else {
		res = pascal(n - 1, m) + pascal(n - 1, m - 1);
		}
	return res;

¿Alguien sabría algo? Yo tengo varías cosas planteadas, pero es bastante laborioso de desarrollar por aquí, por eso quiero esperar a ver si alguien al menos me da una pista o alguna idea de por donde cogerlo.

Muchísimas gracias a todos de antemano.

PD: cuando digo tamaño, me refiero al tamaño del algoritmo. No creo que en este foro haga falta explicarlo XD.

B

[Borrado] #2 Nov '14

Vale que he leído el pd y tal, pero me gustaría asegurarme: por tamaño te refieres a coste en tiempo del algoritmo? Nunca he visto ese concepto, o al menos con ese nombre.

De todas formas, puedes calcular memoizando el valor que te piden. También puedes hacerlo con una sola llamada recursiva si tienes en cuenta que realmente ese triángulo equivale a los coeficientes binomiales.

2

HeXaN #3 Nov '14

¿Te refieres a dar el valor de O (grande) para ese algoritmo?

1

E

ErCordobes #4 Nov '14

Exacto, el objetivo es el coste en tiempo del algoritmo. Pero necisito saber el tamaño, de ahí sacar la ecuacion en concurrencia, hallar las raices y calcular el orden de complejidad de este algoritmo. Pero necesito antes el tamaño, y no lo veo del todo claro cual sería.

Para que quede mas claro, cuando digo tamaño me refiero a las veces que se hace el propio problema( la llamada concurrente). Por ejemplo para fibonacci T(n)= T(n-1)+ T(n+2) + k. Siendo k una constante donde incluiria el tiempo de sumas y demas. Espero que se me entienda, sino intento explicarme aún mejor.

Gracias por vuestra respuestas. Espero que me podais ayudar. XD

Gracias.

1 respuesta

B

[Borrado] #5 Nov '14

#4 Bueno, aquí el problema que tienes es que la recurrencia tiene dos variables.

T(n,m) = T(n-1,m) + T(n-1,m-1) + O(1) si n!=m o m>0, 1 otherwise.

De todas formas, puedes intuir que el coste será exponencial.

Una posible argumentación es que, para cualquier caso con n>m, se puede llegar al caso n=m=1. Sabiendo esto, se puede dar una cota más "permisiva" del coste en tiempo del algoritmo con la siguiente recurrencia simplificada:

T(n) = T(n-1) + T(n-1) + O(1)

Por los teoremas maestros, sabemos que T(n) = O(2ⁿ). De hecho, se puede probar por inducción que se hacen exactamente 2ⁿ - 1 pasos.

No se el nivel de detalle que te exigen, pero lo que he dicho tampoco es "vender humo" del todo.

1 1 respuesta

E

ErCordobes #6 Nov '14

#5 Muchas gracias por responder kyelek. ^^

Te comento una duda que me surge. No me queda claro porque en el caso de la llamada pascal(n-1,m) consideras el tamaño como T(m-1). Me explico, como a la n se le va restando uno en cada llamada recursiva llegará un momento que sea n=m, y ahí habremos llegado al caso base y terminado por así decirlo. Es de ahí de donde viene todas mis dudas, ya que el número de llamadas hasta que n=m sería (n-1)-m ¿no?. Es por eso que no se cómo expresarlo. En el segundo caso de pascal(n-1,m-1) si que lo veo claro, puesto que la m llegara un momento que valdrá cero y llegaremos a un caso base. Por lo tanto el tamaño es lógico que sea T(m-1).

Espero que me puedas aclarar esta duda. Muchas gracias compañero.

1 respuesta

B

[Borrado] #7 Nov '14

#6 Perdón, en la recurrencia "mágica", cambia m por n.

Si calculas el coste en base a esa recurrencia, lo que obtienes es una cota (bastante) superior al número de llamadas recursivas que haces en realidad. La causa principal de esto es el caso n=m.

De todas formas, no se si te piden que calcules los números del triángulo de Pascal de esa forma explicítamente. Si no es el caso, puedes hacerlo con una sola llamada recursiva.

Si te fijas, puedes "fijar" la n y obtener la siguiente fórmula:

(n choose k+1) = (n choose k)*(n-k)/(k+1)

La cual solo depende de un parámetro, haciendo lineal el cálculo.

1 1 respuesta

E

ErCordobes #8 Nov '14

#7 Buenas ^^. Gracias de nuevo.

Sí, creo que me piden que lo calcule así, pasando dos parámetros de entrada al método/función. La cuestión es que lo de m=n, me confunde mucho. En el enunciado del ejercicio me dice lo siguiente:

"Defina el tamaño del problema (para facilitar, no tiene por qué considerar que el tamaño es pequeño cuando n=m), calcule de manera justificada el T(n) y la complejidad del algoritmo del apartado anterior."

Lo que señalo en negrita no se muy bien lo que quiere decir con esto...No se si cambia algo en como lo has venido planteando hasta ahora.

Yo en un principio lo plantee así, como has dicho: T(n)= 2T(n-1)+k pero empezé a darle vueltas y ahora mismo no le veo sentido.... :wtf:

¿A qué te refieres exactamente con lo de "llamada mágica"?

Un saludo y gracias, soy un pesado. Lo siento :palm:

1 respuesta

B

[Borrado] #9 Nov '14

#8 El sentido que tiene T(n) = T(n-1) + T(n-1) viene por lo que mencioné antes; se puede llegar al caso n=m=1 con cualquier caso n > m.

Si dibujaras los árboles de recursión de la recurrencia de dos variables verías que sería un árbol "podado" respecto al que obtendrías si dibujaras el mismo árbol para T(n). Es decir, el número de nodos que tendrá el árbol real estará acotado superiormente por T(n) = 2ⁿ -1.

Lo que supongo te dicen con lo que remarcas en negrita es que, para simplificar, no tengas en cuenta precisamente esto.

De todas formas, si lo que te piden es pasar dos parámetros como entrada, puedes hacerlo de la forma lineal, pero dejando uno fijado en todas las llamadas.

1 1 respuesta

E

ErCordobes #10 Nov '14

#9 Muchas gracias por toda tu ayuda kyelek.

Sólo una última caso en la llamada pascal(n-1, m-1) no llegará a ser n=m, sino que m=0, puesto que que n>m. Y será el tamaño de m el que condicione el tamaño de ese subproblema ¿no?. Es lo que no llego a comprender.

Muchas gracias por todo. Me has ayudado un montón. Gracias.

1 respuesta

B

[Borrado] #11 Nov '14

#10 Sí, en caso es m quién condiciona el tamaño. Pero como hemos supuesto que n>m, sigue siendo cierto lo de la cota superior.

1 1 respuesta

E

ErCordobes #12 Nov '14

#11 Vale ^^. Aclarado, muchísimas gracias por todo . Eres un ¡fenómeno! XD

Saludos.

Duda sobre Tamaño de un Algoritmo

Usuarios habituales

Tags