Algorithms review 5 Greedy Algorithms
This is a personal notes of algorithms courses
Optimization problem#
We are to make a change of $0.40 using US currency and assuming that there is an unlimited supply of coins.
Like the graph shown before, the height of the tree would be $h$, and the total time complexity of all choices would be $O(4^h)$. But we only need the most optimal choice, we always choose the coin which has the largest value. Then our choice will become $40 = 25+30+5$. The greedy algorithms is that instead we go through the whole tree, we only go through a single branches. Then the time compleity would be lower to $O(h)$.