What do programmers mean when they use the term "BruteForce approach to the problem "?

Question

I wanted to understand what do programmers generally mean when they use the term " Brute Force " in their work .

Answer 1

Brute force is the application of a naïve algorithm to a problem, relying on computational resources instead of algorithmic efficiency to make the problem tractable.

@Guy Coder is correct that it often comes up when searching a data set, but it can be applied to other types of problems as well.

For example, supposed you needed to reverse the order of a linked list. Consider these approaches:

1. Adjust the pointers between the elements so that they are linked in the reverse order. That can be done in linear time with a fixed amount of memory.

2. Create a new list by walking the original list and pre-pending a copy of each element, then throw away the old list. That can also be done in linear time (though the constant will be higher) but it also uses memory in proportion to the length of the list.

3. Systematically create all possible linked lists until you discover one that's the reverse of the original list. It's an exhaustive search over an unbounded solution space (which is different than an exhaustive search of a finite data set). Since there are an infinite number of linked lists to try, no matter how much computing resource you can apply, it might never finish.

4. Like 3, but revised to generate and test all possible linked lists of the same length as the original list. This bounds the solution space to O(n!), which can be huge but is finite.

5. Start coding without an understanding of how to solve the problem, and iterate away until something works.

"Brute force" is technical slang rather than jargon with a precise definition. For different people, it will carry different connotations. Which of these solutions you consider to be "brute force" depends on what the term connotes for you.

For me, and many of the programmers and software engineers I've worked with, "brute force" carries these connotations:

• The application of brute force is an intentional engineering decision. Brute force might be selected because:

  • The brute force method is easy to get correct
  • To create a reference implementation to check the results of a more efficient algorithm
  • The more efficient algorithm is not known
  • The more efficient algorithm is hard to implement correctly
  • The size of the problem is small enough that there is not much difference between brute force and the clever algorithm

• A brute force solution must solve the problem. An implementation that attempts an exhaustive search of an unbounded space is not a general solution to the problem.

• "Brute force" is usually a superlative. We say, "I used the brute force solution" rather than "a brute force solution." The implication is that, for a given problem, there's one straight-forward, direct, and obvious algorithm most programmers would recognize (or come up with) as the brute force solution for a given problem.

For those like me who feel the term has all of these connotations, only approach #2 is brute force. Those who disagree aren't wrong. For them, the term carries different connotations.

Answer 2

Many programming problems are a search of a data space, E.g. a walk of a list, tree, graph, etc. In solving the problem all of the data is searched or walked.

If one wants to make the code faster they will start to notice patterns that can be used to remove unnecessary parts of the search space.

When code searches the entire space that is "brute force". When optimizations are used to make the search more efficient that is not "brute force".

In other works when you first start writing code for an unknown problem you will start with brute force and then as you learn tricks (find optimizations) it will no longer be brute force.

As example, if one needs to find the first entry with just 1 in a list. The brute force method would search the entire list even after finding the first 1. But if one knows that only the first 1 needs to be found as soon as it is found then searching the remainder of the list is not needed.

Answer 3

A brute force approach to a problem is analogous to...

Forcing the door instead of picking the lock;

Hammering in a screw;

Executing all the suspects instead of determining who is guilty;

Fishing with dynamite;

Drawing with a grid;

Decorating ostentatiously instead of tastefully;

Victory through overwhelming numbers; or ...

Applying vast computational resources to a problem instead of finding an efficient solution.