Curso 2024/2025
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.