complejidad de algoritmos

en la wikipedia seguro que lo pone

Programación dinámica es lo de 'divide y vencerás', ¿ no ?
Teniendo como recurrencia inicial


El coste es:



Los de backtracking es exponencial.

El otro no me suena.

Bueno creo que estoy bastante seguro de que esta es la solucion:

Backtraking nxn= n^2 (profundidad x anchura de los nodos a visitar)

Programación Dinámica: nxn=n^2 (se construye una matriz con todas las subsoluciones)

Gready: n^2 (Este depende del algoritmo de ordenación que haya usado, en mi caso, un SelectionSort de complejidad nxn=n^2)

Bueno, eso es todo gracias igualmente y si podeis aportar más información pues mejor.

saludos!

eTc_84 escribió:Programación dinámica es lo de 'divide y vencerás', ¿ no ?
Teniendo como recurrencia inicial

t(n)=a.t(n/b)+c.n^b

El coste es:

t (n) O(n^logb(a)) si a > bd
t (n) O(n^d.log(n)) si a = bd
t (n) O(n^d) si a < bd

Los de backtracking es exponencial.

El otro no me suena.

No es lo mismo programación dinámica que divide y vencerás, y respecto a la complejidad del algoritmo... tendrá que ver con que tipo de problema te encuentres.

No tiene la misma complejidad hacer por divide y vencerás un quicksort que un "vete tu a saber".


No tiene la misma complejidad tampoco hacer una cosa X con algoritmos voraces que una cosa Y.

Salu2

4eVaH escribió:

No es lo mismo programación dinámica que divide y vencerás, y respecto a la complejidad del algoritmo... tendrá que ver con que tipo de problema te encuentres.

No tiene la misma complejidad hacer por divide y vencerás un quicksort que un "vete tu a saber".


No tiene la misma complejidad tampoco hacer una cosa X con algoritmos voraces que una cosa Y.

Salu2

Exacto. Lo que has puesto son tipos de algoritmos, es decir, clasificaciones de los mismos. Y dentro de esos tipos hay distintos algoritmos con una complejidad generalmente similar, pero no idéntica.

Por cierto, cual creis que hace un mayor uso de la memoria? Es decir, cual gasta más memoria?

Bajo mi punto de vista:

programación dinámica>backtracking>greedy

A ver que opinais

Veamos, una aclaracion, en el Back-Tracking lo que se intenta es no pasar por todos los nodos del arbol, porque si lo visitas todos estarias haciendo "Fuerza Bruta", y lo que se pretende con los algoritmos de vuelta atras es totalmente lo contrario. Tambien depende muchisimo de la entrada del problema, habra veces que el algoritmo te de una respuesta muy rapida y otras que quizas llegue a ser fuerza bruta sin ningun resultado. No confundir con el tamaño del problema, pues es indudable que resolver un laberinto (por ejemplo) con 50.000 habitaciones que uno con 40, pero eso si, si en el de 50.000 habitaciones no puedes moverte de donde empiezas y el de 40 tiene una solucion 'normal' pues el de 50.000 tardaria muchisimo menos que el otro.

Bueno, un saludo.

Carlos A. escribió:Veamos, una aclaracion, en el Back-Tracking lo que se intenta es no pasar por todos los nodos del arbol, porque si lo visitas todos estarias haciendo "Fuerza Bruta", y lo que se pretende con los algoritmos de vuelta atras es totalmente lo contrario. Tambien depende muchisimo de la entrada del problema, habra veces que el algoritmo te de una respuesta muy rapida y otras que quizas llegue a ser fuerza bruta sin ningun resultado. No confundir con el tamaño del problema, pues es indudable que resolver un laberinto (por ejemplo) con 50.000 habitaciones que uno con 40, pero eso si, si en el de 50.000 habitaciones no puedes moverte de donde empiezas y el de 40 tiene una solucion 'normal' pues el de 50.000 tardaria muchisimo menos que el otro.

Bueno, un saludo.

es que backtracking viene a ser fuerza bruta.. que yo sepa si empezamos a podar hijos y demás estaríamos hablando de Branch and Bound...

saludos

AlterElt escribió:Por cierto, cual creis que hace un mayor uso de la memoria? Es decir, cual gasta más memoria?

Bajo mi punto de vista:

programación dinámica>backtracking>greedy

A ver que opinais

De hecho programación dinámica es un tipo de programación cuya filosofía es la siguiente: "Vamos a aprovechar un recurso mas barato para minimizar el uso del otro" Esto es espacio en memoria vs tiempo de ejecución.

Un algoritmo en programación dinámica hace abuso de memoria (recurso más bien barato) para conseguir tiempos de ejecución más bajos (el tiempo es oro).

Salu2


PD: Respecto a Backtracking... hay 3 esquemas de backtracking, uno que nos da una solución al problema (complejidad más baja de los 3) otro que nos da la mejor solución al problema, la óptima (complejidad media de los 3) otro que nos da TODAS las soluciones (este si es casi como hacerlo por fuerza bruta, pero usando los esquemas backtracking).