Brute Force Algorithms are exactly what they sound like – straightforward methods of solving a problem that rely on sheer computing power and trying every possibility rather than advanced techniques to improve efficiency.
For example, imagine you have a small padlock with 4 digits, each from 0-9. You forgot your combination, but you don't want to buy another padlock. Since you can't remember any of the digits, you have to use a brute force method to open the lock.
So you set all the numbers back to 0 and try them one by one: 0001, 0002, 0003, and so on until it opens. In the worst case scenario, it would take 104, or 10,000 tries to find your combination.
A classic example in computer science is the traveling salesman problem (TSP). Suppose a salesman needs to visit 10 cities across the country. How does one determine the order in which those cities should be visited such that the total distance traveled is minimized?
The brute force solution is simply to calculate the total distance for every possible route and then select the shortest one. This is not particularly efficient because it is possible to eliminate many possible routes through clever algorithms.
The time complexity of brute force is O(mn), which is sometimes written as O(n*m) . So, if we were to search for a string of "n" characters in a string of "m" characters using brute force, it would take us n * m tries.
More information about algorithms
In computer science, an algorithm is simply a set of step by step procedure to solve a given problem. Algorithms can be designed to perform calculations, process data, or perform automated reasoning tasks.
Here's how Wikipedia defines them:
An algorithm is an effective method that can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive states, eventually producing “output” and terminating at a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate random input.
There are certain requirements that an algorithm must abide by:
- Definiteness: Each step in the process is precisely stated.
- Effective Computability: Each step in the process can be carried out by a computer.
- Finiteness: The program will eventually successfully terminate.
Some common types of algorithms include:
- sorting algorithms
- search algorithms
- compression algorithms.
Classes of algorithms include
- Dynamic Programming
- Computational Geometry
Although technically not a class of algorithms, Data Structures are often grouped with them.
Algorithms are most commonly judged by their efficiency and the amount of computing resources they require to complete their task.
A common way to evaluate an algorithm is to look at its time complexity. This shows how the running time of the algorithm grows as the input size grows. Since the algorithms today have to operate on large data inputs, it is essential for our algorithms to have a reasonably fast running time.
Sorting algorithms come in various flavors depending on your necessity. Some, very common and widely used are:
There is no sorting discussion which can finish without quick sort. Here is the basic concept: Quick Sort
A sorting algorithm which relies on the concept how to sorted arrays are merged to give one sorted arrays. Read more about it here: Mergesort
freeCodeCamp’s curriculum heavily emphasizes creating algorithms. This is because learning algorithms is a good way to practice programming skills. Interviewers most commonly test candidates on algorithms during developer job interviews.
- Covers object oriented programming, prototypal inheritance, sorting & searching algorithms, quicksort, mergesort, binary search trees and advanced algorithm concepts
- ISBN-13: 978-1785285493
- Covers recursion, sorting and searching algorithms, linked lists and binary search trees.
- ISBN-13: 978-1449364939