Duda tamaño de un algoritmo.

Archivado
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:

Imagen

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):

Imagen

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.
Hola, tiros al azar

http://pinguinazos.blogspot.com.es/2011 ... -en-c.html
http://www.solveet.com/exercises/Triang ... lution-267
http://ingenieropaulo.blogspot.com.es/2 ... arp-c.html
http://vixra.org/pdf/1307.0051v1.pdf

No sé nada del tema pero en esta página quizá te puedan guiar en profundidad,

Tambien hay una serie de conversores y calculadoras de algoritmos en linea.

http://www.e-matematicas.net/algebra/lo ... peraciones
http://ideone.com/


Un saludo
el_fumador_2008 escribió:Hola, tiros al azar

http://pinguinazos.blogspot.com.es/2011 ... -en-c.html
http://www.solveet.com/exercises/Triang ... lution-267
http://ingenieropaulo.blogspot.com.es/2 ... arp-c.html
http://vixra.org/pdf/1307.0051v1.pdf

No sé nada del tema pero en esta página quizá te puedan guiar en profundidad,

Tambien hay una serie de conversores y calculadoras de algoritmos en linea.

http://www.e-matematicas.net/algebra/lo ... peraciones
http://ideone.com/


Un saludo


Muchas gracias por responder ^^.

Los links que me has pasado se trata del código del algoritmo a secas (de forma iterativa). Pero lo que yo busco es el orden de complejidad del algoritmo, pero en vez de en forma iterativa, en recursiva. Me explico mejor, se trata de analizar el algoritmo y hallar la eficiencia que tendría por así decirlo.

De todas formas muchas gracias por tu ayuda compañero, se agradece mucho. XD XD
No lo tengo muy fresco, pero creo recordar que siempre puedes hacer una aproximación empírica de la complejidad del algoritmo basándote en los tiempos de ejecución para diferentes tamaños de n, y extrapolar la función.

O mirar en Internet. http://stackoverflow.com/questions/2202 ... s-triangle .

O( (n + m)! / (n! m!) )
mariobros_95 escribió:
el_fumador_2008 escribió:Hola, tiros al azar

http://pinguinazos.blogspot.com.es/2011 ... -en-c.html
http://www.solveet.com/exercises/Triang ... lution-267
http://ingenieropaulo.blogspot.com.es/2 ... arp-c.html
http://vixra.org/pdf/1307.0051v1.pdf

No sé nada del tema pero en esta página quizá te puedan guiar en profundidad,

Tambien hay una serie de conversores y calculadoras de algoritmos en linea.

http://www.e-matematicas.net/algebra/lo ... peraciones
http://ideone.com/


Un saludo


Muchas gracias por responder ^^.

Los links que me has pasado se trata del código del algoritmo a secas (de forma iterativa). Pero lo que yo busco es el orden de complejidad del algoritmo, pero en vez de en forma iterativa, en recursiva. Me explico mejor, se trata de analizar el algoritmo y hallar la eficiencia que tendría por así decirlo.

De todas formas muchas gracias por tu ayuda compañero, se agradece mucho. XD XD


Muy fácil: n*m.

Saludos.
DJTesto escribió:
mariobros_95 escribió:
el_fumador_2008 escribió:Hola, tiros al azar

http://pinguinazos.blogspot.com.es/2011 ... -en-c.html
http://www.solveet.com/exercises/Triang ... lution-267
http://ingenieropaulo.blogspot.com.es/2 ... arp-c.html
http://vixra.org/pdf/1307.0051v1.pdf

No sé nada del tema pero en esta página quizá te puedan guiar en profundidad,

Tambien hay una serie de conversores y calculadoras de algoritmos en linea.

http://www.e-matematicas.net/algebra/lo ... peraciones
http://ideone.com/


Un saludo


Muchas gracias por responder ^^.

Los links que me has pasado se trata del código del algoritmo a secas (de forma iterativa). Pero lo que yo busco es el orden de complejidad del algoritmo, pero en vez de en forma iterativa, en recursiva. Me explico mejor, se trata de analizar el algoritmo y hallar la eficiencia que tendría por así decirlo.

De todas formas muchas gracias por tu ayuda compañero, se agradece mucho. XD XD


Muy fácil: n*m.

Saludos.


No es tan f'acil, de hecho esa no puede ser la complejidad de la funci'on recursiva que ha pegado.

Lo dicho, te invito a que miras el post de stackoverflow que te pegu'e ayer.
squarewave escribió:No lo tengo muy fresco, pero creo recordar que siempre puedes hacer una aproximación empírica de la complejidad del algoritmo basándote en los tiempos de ejecución para diferentes tamaños de n, y extrapolar la función.

O mirar en Internet. http://stackoverflow.com/questions/2202 ... s-triangle .

O( (n + m)! / (n! m!) )



Muchas gracias compañero. En el enunciado me indica que para mayor facilidad en su cálculo no tengo porque considerar que el tamaño es pequeño cuando n=m. Esto junto con que n>m, he considerado:
T(n)= T(n-1)+T(n-1)+0(1) -------> T(n)=2T(n-1)+k

Y resolviendo la ecuación de recurrencia por el teorema maestro, o de forma general (en ambos casos sale el mismo resultado, logicamente) me da una complejidad de 2^n.

¿Que opinas de esta solución? Muchas gracias por tu ayuda squarewave.
DJTesto escribió:
mariobros_95 escribió:
el_fumador_2008 escribió:Hola, tiros al azar

http://pinguinazos.blogspot.com.es/2011 ... -en-c.html
http://www.solveet.com/exercises/Triang ... lution-267
http://ingenieropaulo.blogspot.com.es/2 ... arp-c.html
http://vixra.org/pdf/1307.0051v1.pdf

No sé nada del tema pero en esta página quizá te puedan guiar en profundidad,

Tambien hay una serie de conversores y calculadoras de algoritmos en linea.

http://www.e-matematicas.net/algebra/lo ... peraciones
http://ideone.com/


Un saludo


Muchas gracias por responder ^^.

Los links que me has pasado se trata del código del algoritmo a secas (de forma iterativa). Pero lo que yo busco es el orden de complejidad del algoritmo, pero en vez de en forma iterativa, en recursiva. Me explico mejor, se trata de analizar el algoritmo y hallar la eficiencia que tendría por así decirlo.

De todas formas muchas gracias por tu ayuda compañero, se agradece mucho. XD XD

Muy fácil: n*m.

Saludos.


No es tan f'acil, de hecho esa no puede ser la complejidad de la funci'on recursiva que ha pegado.

Lo dicho, te invito a que miras el post de stackoverflow que te pegu'e ayer.


Buenas:

http://stackoverflow.com/questions/2575 ... ve#tab-top

Edición: Añado este paper. Primera página, último párrafo: triángulo de pascal de forma recursiva.

http://webcourse.cs.technion.ac.il/2342 ... rial11.pdf

Edición 2: Añado otra fuente. Página 83 tabla 4.3. Complejidad de las distintas implementaciones del triángulo, en este caso, la recursiva.

http://books.google.es/books?id=2z29BAA ... ty&f=false

Edición 3: http://delab.csd.auth.gr/papers/SBI02m.pdf Página 2 segundo párrafo.

Edición 4: http://www.lcc.uma.es/~av/Libro/CAP5.pdf Página 180. Segundo párrafo.

Edición 5: http://www.cs.uns.edu.ar/~prf/teaching/ ... namica.pdf Cuarta slide, primera frase.

Edición 6: http://es.wikipedia.org/wiki/Programaci ... binomiales: "es posible diseñar un algoritmo con un tiempo de ejecución de orden O(nk) basado en la idea del Triángulo de Pascal "


Saludos.
DJTesto escribió:
Buenas:

http://stackoverflow.com/questions/2575 ... ve#tab-top

Edición: Añado este paper. Primera página, último párrafo: triángulo de pascal de forma recursiva.

http://webcourse.cs.technion.ac.il/2342 ... rial11.pdf

Edición 2: Añado otra fuente. Página 83 tabla 4.3. Complejidad de las distintas implementaciones del triángulo, en este caso, la recursiva.

http://books.google.es/books?id=2z29BAA ... ty&f=false

Edición 3: http://delab.csd.auth.gr/papers/SBI02m.pdf Página 2 segundo párrafo.

Edición 4: http://www.lcc.uma.es/~av/Libro/CAP5.pdf Página 180. Segundo párrafo.

Edición 5: http://www.cs.uns.edu.ar/~prf/teaching/ ... namica.pdf Cuarta slide, primera frase.

Edición 6: http://es.wikipedia.org/wiki/Programaci ... binomiales: "es posible diseñar un algoritmo con un tiempo de ejecución de orden O(nk) basado en la idea del Triángulo de Pascal "


Saludos.


Muchas gracias DJTesto a tí también por la ayuda. XD XD

Por lo tanto, 2^n es una complejidad posible ¿no? O al menos eso observo en los links que has pasado.

Saludos y muchas gracias de antemano.
Hola mariobros_95, creo que tienes razon en el 2T(n-1)+k, aunque la explicación con la que yo he dado es que el tiempo de ejecución que te piden es T(n), solo n, por lo que se ignora la m (no tiene que ver n=m o m<n) así que tiene toda la pinta de que el resultado que te ha dado sea el correcto.
9 respuestas
Archivado
Volver a General