Overview
In this tutorial, we will learn about different types of algorithms and classify them based on problem-solving techniques.
Types of Algorithms
Some types of algorithms are as follows:
- Brute force algorithm
- Recursive algorithm
- Divide & Conquer algorithm
- Backtracking algorithm
- Greedy algorithm
- Dynamic programming algorithm
- Randomized algorithm
Brute force algorithm
A brute force algorithm tries all the possibilities until a satisfactory solution is found.
Recursive algorithm
A recursive algorithm is an algorithm that calls itself in its own steps. A recursive algorithm does the following:
- It solves the base case/s directly. A base case is a straightforward case that doesn’t use recursion.
- Calls itself using a simple subproblem
- Performs some work to convert the solution to the
subproblem into a solution to the actual given problem
Divide & Conquer algorithm
A divide & conquer algorithm consists of two parts:
- Divide the problem into smaller sub-problems, and solve these sub-problems recursively
- Combine the solutions to the subproblems into a solution to the original problem
Backtracking algorithm
The backtracking algorithm explores all possible choices or decisions one at a time and then “backtracks” from a choice that does not lead to a valid solution.
Dynamic programming algorithm
A dynamic programming algorithm uses memoization. It remembers past results and uses them to find new results. Dynamic programming algorithms are generally used for optimization problems.
Greedy algorithm
A greedy algorithm works in phases. At each phase:
- Take the best that you can get at that moment, without regard for
future consequences - Hope that by choosing a local optimum at each step, you will end up at a global optimum
Randomized algorithm
A randomized algorithm uses a random number at least once during the computation to make a decision.