Greedy Algorithms

A greedy algorithm constructs a solution to the problem by always making a choice that looks the best at the moment.

• Greedy algorithms are usually very efficient
• The difficulty is find a greedy strategy that always produces a global optimal solution to the problem
• Often difficult to argue that a greedy algorithm works

Definition

• An algorithm that, while executing, selects only the information that meets a certain criteria.
• The general five components, taken from Wikipedia:
  • A candidate set, from which a solution is created.
  • A selection function, which chooses the best candidate to be added to the solution.
  • A feasibility function, that is used to determine if a candidate can be used to contribute to a solution.
  • An objective function, which assigns a value to a solution, or a partial solution.
  • A solution function, which will indicate when we have discovered a complete solution.

What you need to know

• Used to find the expedient, though non-optimal, solution for a given problem.
• Generally used on sets of data where only a small proportion of the information evaluated meets the desired result.
• Often a greedy algorithm can help reduce the Big O of an algorithm

Pseudo Code of a Greedy Algorithm to Find Largest Difference of any Two Numbers in an Array

greedy algorithm (array)
  var largest difference = 0
  var new difference = find next difference (array[n], array[n+1])
  largest difference = new difference if new difference is > largest difference
  repeat above two steps until all differences have been found
  return largest difference

This algorithm never needed to compare all the differences to one another, saving it an entire iteration.