Algorithms For Dummies

  Considering Algorithm Design 

     29

their core: to use steps to solve problems one small piece at a time. The following 

sections help you understand the divide-and-conquer approach to problem solv-

ing in more detail.

Avoiding brute-force solutions

A brute-force solution is one in which you try each possible answer, one at a time, 

to locate the best possible answer. It’s thorough, this much is certain, but it also 

wastes time and resources in most cases. Testing every answer, even when it’s 

easy to prove that a particular answer has no chance of success, wastes time that 

an algorithm can use on answers that have a better chance of success. In addition, 

testing the various answers using this approach generally wastes resources, such 

as memory. Think of it this way: You want to break the combination for a lock, so 

you begin at 0, 0, 0, even though you know that this particular combination has 

no chance of success given the physical characteristics of combination locks. A 

brute-force solution would proceed with testing 0, 0, 0 anyway and then move on 

to the equally ridiculous 0, 0, 1.

It’s important to understand that every solution type does come with advantages, 

sometimes quite small. A brute-force solution has one such advantage. Because 

you test every answer anyway, you don’t need to perform any sort of preprocess-

ing  when  working  with  a  brute-force  solution.  The  time  saved  in  skipping  the 

preprocessing, though, is unlikely to ever pay back the time lost in trying every 

answer. However, you may find occasion to use a brute-force solution when