Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2024/2025

Costes del ejercicio 6 del tema 5.3

Los dos algoritmos obtenidos empleando Programación Dinámica tienen los siguientes costes en el peor caso, siendo n la cantidad de objetos y p el peso máximo:

Recursivo No recursivo
Coste temporal O(n · p) O(n · p)
Coste espacial O(n · p) O(n · p)

Una diferencia entre el algoritmo recursivo y el no recursivo en este problema es que el no recursivo calcula resultado[objeto][pesoDisponible] para todas las celdas de la tabla resultado, mientras que el recursivo a lo sumo hace O(2n) llamadas para calcular celdas, y O(2n) podría ser menor que O(n · p) si p es suficientemente grande. No obstante, en cualquier caso en el algoritmo recursivo también pagamos un coste temporal O(n · p) inicialmente para poner -1 en todas las celdas.