Greedy Algorithms

There are many definitions of greedy algorithms, but in general, they have two properties:

• You build the solution by finding the most optimal answer at each local step.
• As you go through each local step, you do not backtrack; the answer you've picked for all of the previous steps remain the same.

Greedy algorithms are not the same as dynamic programming, simply because in dynamic programming, you may re-visit previous steps in order to build the most optimal global answer.

This means that greedy algorithms cannot guarantee the most optimal global answer for every algorithm. It can produce a very slow global solution depending on the algorithm. But for a small subset of algorithms, greedy algorithms can produce the best solution and most importantly, it can produce that solution easily and efficiently.

Characteristics:

• Easy to write
  • Greedy algorithms are often simple in nature, usually consisting of one simple loop
  • Because it is so easy to write, greedy algorithms are a nice starter / brute-force solution when brainstorming ways to optimize the solution to a problem.
• Efficient
  • If the data is constructed in a specific way, the greedy algorithm itself is very fast. For example, consider sorting vs. not sorting some data before iterating through it. Greedy algorithms can take advantage of the sorted property to deliver a very efficient outcome.
• Not ideal for all
  • Greedy algorithms can sometimes lead to poor performance, or even horrible performance depending on the nature of the problem that is to be solved.
  • Consider a BST with integer nodes -- can you think of one example case of greedy algorithms failing to retrieve the largest root->leaf sum path?