Algoritmos y Estructuras de Datos (VJ1215)

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:

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(2ⁿ) llamadas para calcular celdas, y O(2ⁿ) 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.