A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Greedy Algorithms

This next tactic can speed up some of the most stubborn algorithms. It doesn’t work in every situation, but when it does, it can be a game changer.

Let’s talk about writing greedy algorithms.

This may sound like a strange term, but here’s what it means. A greedy algorithm is one that, in each step, chooses what appears to be the best option at that moment in time. This will make sense with a basic example.

Array Max

Let’s write an algorithm that finds the greatest number in an array. One way we can do this is to use nested loops and check each number against every other number in the array. When we find the number that is greater than every other number, it means we’ve found the greatest number in the array.

As is typical for ...