Created: 2014-05-19 11:18
Updated: 2014-06-06 11:16


#Trainning & Reference: Data Structures.


  • Recursion O(2^n) complexity
  • Dynamic O(W*n) complexity
  • Memory Function (Recursion + Dynamic) O(W*n - constant) (unimplemented). In general, we cannot expect more than a constant-factor gain in using the memory function method for the knapsack problem, because its time efficiency class is the same as that of the bottom-up algorithm. A more significant improvement can be expected for dynamic programming algorithms in which a computation of one value takes more than constant time. You should also keep in mind that a memory function algorithm may be less space-efficient than a space-efficient version of a bottom-up algorithm. -- Introduction to the Design and Analysis fo Algorithms 3rd Edition: page 296.
  • Sources:


  • Source code - Trainning from class.
Cookies help us deliver our services. By using our services, you agree to our use of cookies Learn more