3 ms·
This isn't really what the article is about, but I don't think that the term "Greedy algorithm" means what the author thinks. Greedy algorithms are about makin
by Negitivefrags 2y ago
This isn't really what the article is about, but I don't think that the term "Greedy algorithm" means what the author thinks.
Greedy algorithms are about making locally optimal choices.
They are not "brute force" algorithms or inefficient ones.
In fact, greedy algorithms are almost always faster. They are faster because they consider only local information instead of the entire data set. In exchange for that, a greedy algorithm may produce non-optimal answers.
- adamgordonbell 2y agoYeah, greedy is not what he thinks it is. I think of change making algorithm when working retail. Greedy is you always use the largest coin you can, and then the next largest and so on. It works with sensible coin denominations but there are sets of coins where the greedy algorithm is not optimal.
- o11c 2y agoRelevant link: https://en.wikipedia.org/wiki/Change-making_problem https://en.wikipedia.org/wiki/Change-making_problem Looking at cases where greedy isn't optimal, I see two patterns. Either: * there are two coins close in value (ratio of less than 2), e.g. both 20¢ and 25¢; or * there is a "missing" coin at the GCD of two larger coins. I'm pretty sure you can precompute extra "virtual coins" (e.g. 40¢) to make greedy optimal again, but you have to place restrictions on how many of them you're allowed to use.