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 filas y m la cantidad de columnas:

El coste temporal corresponde a rellenar las n · m celdas de la matriz de resultados invirtiendo tiempo O(1) por cada una de ellas.

El coste espacial viene dado por el tamaño de la matriz de datos y de la matriz de resultados. En el algoritmo recursivo ese coste es superior al empleado por la pila de llamadas, pues no puede haber más llamadas de la función recursiva activas que celdas en la matriz (también puede razonarse que a lo sumo hay m + n - 1 llamadas activas).

En el algoritmo no recursivo se podría reducir a dos filas o dos columnas el coste espacial de la matriz de resultados si lo único que nos interesa es la cantidad de puntos máxima, pero el coste espacial total seguiría siendo O(n · m) debido al tamaño de la matriz de datos.