CODEWITHSUNDEEP
c++data-structuresdynamic-programmingmemoization
Tushar Bhatt
Tushar Bhatt

Reputation: 1

Ways to memoize in c++, Dynamic programming

I am fairly new to dynamic programming, i have seen people, memoize in javascript using objects. But i would like to know what will be the most efficient way to memoize in c++. Which data structure should i use, is map good? orr is there something better, please let me know.

Upvotes: 0

Views: 326

Answers (1)

Job_September_2020
Job_September_2020

Reputation: 880

I think you should use unordered_map instead of map.

The reason is that the time complexity for the search operation are as follow:

  • unordered_map = O(1)
  • map = O(log(N))

The reason is that unordered_map works as a hash table while map works as a binary tree.

Similarly, you can also use unordered_set instead of set for the same reason:

The time complexity for the search operation are as follow:

  • unordered_set = O(1)
  • set = O(log(N))

Upvotes: 2

Related Questions