Change-Making Problem: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 6: | Line 6: | ||
== Parameters == | == Parameters == | ||
n: number of coin denominations | $n$: number of coin denominations | ||
S: sum to be made | $S$: sum to be made | ||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 22: | Line 22: | ||
| [[Dynamic Programming (Change-Making Problem Change-Making Problem)|Dynamic Programming]] || 1953 || | | [[Dynamic Programming (Change-Making Problem Change-Making Problem)|Dynamic Programming]] || 1953 || | ||
|- | |- | ||
| [[Probabilistic Convolution Tree (Change-Making Problem Change-Making Problem)|Probabilistic Convolution Tree]] || 2014 || | | [[Probabilistic Convolution Tree (Change-Making Problem Change-Making Problem)|Probabilistic Convolution Tree]] || 2014 || $O(n \log n) | ||
|- | |- | ||
|} | |} | ||
Revision as of 09:24, 10 April 2023
Description
Given an unlimited amount of coins of denominations
Parameters
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Brute Force | 1940 | Exact | Deterministic | |||
| Dynamic Programming | 1953 | Exact | Deterministic | Time | ||
| Probabilistic Convolution Tree | 2014 | Deterministic | Time & Space |
Time Complexity Graph
Space Complexity Graph
Time-Space Tradeoff
