Classification of algorithms
Classification by purpose
Every algorithm has a purpose. For example, the goal of a quick sort algorithm is to sort data in ascending or descending order. But goals are infinite in number, so we group them by type.
Classification by implementation
The same algorithm can be implemented according to different basic principles.
- Recursion or iteration
The recursive algorithm calls itself repeatedly until the condition is met. This is a common method in functional programming.
Iterative algorithms use loops.
Depending on the problem, this or that implementation is most suitable. For example, the Hanoi Towers problem is best understood in recursive form. But each recursive version has an iterative equivalent and vice versa.
- Logic or procedure
The algorithm can also be thought of as a manageable logical deduction.
The logical component expresses the axioms that the process will use, and the control component determines how the deductions apply to the axioms.
This is the basis of logical programming. Pure logical programming languages have predetermined control, it remains to express only axioms.
- Serial or parallel
In general, it is assumed that the instructions of the algorithms are executed one after another, and we are talking about a sequential algorithm, but they can also be parallel, when the computer architecture allows you to process several instructions at the same time.
In this case, the task is divided into subtasks assigned to different processors. Iterative algorithms are parallelizable, especially sorting algorithms.
- Deterministic or not
Deterministic algorithms perform a predetermined process to solve a problem, while non-deterministic algorithms must guess the best solution at each step. using heuristics.
Classification by design paradigm
Design paradigm - a study area or class of tasks that require a certain type of algorithm.
- Divide and conquer
The divide-and-conquer principle recursively reduces a problem to a simpler case or set of subtasks until it reaches a sufficient level of simplicity for a simple solution. The merge sort algorithm is one example. The sorted list is divided into sublists sorted separately.
The search for a dichotomy is another example based on the same principle.
- Dynamic programming
The shortest path on a weighted graph can be found using the shortest path between adjacent edges.
When the optimal solution to the problem is obtained from the optimal solutions of subtasks, dynamic programming avoids recalculating already solved solutions.
- The main difference from the "divide and conquer" approach is that in the latter subtasks are independent, while in dynamic programming superposition is possible.
- ProgDynamic ram and memorization go hand in hand. The difference with direct recursion is caching, or remembering recursive calls. It's not helpful when subtasks are independent. Otherwise, memorizing the table of previously solved problems reduces the complexity from exponential to polynomial.
- Greedy method
This is analogous to dynamic programming, with the difference that the solutions to the subtasks need not be known at every stage of processing. On the contrary, a "greedy" choice is made, which consists in making the best possible decision at that moment. An example is Kruskal's algorithm.
- Linear programming
The problem is expressed as a set of linear inequalities, then we try to maximize or minimize the input. This can solve many problems, including the maximum flow problem on a directed graph, in particular using a simplex algorithm.
A variant called integer programming consists of restricting the solution space to integers.
- Contraction.
Consists of turning one problem into another, easier to solve.
A simple example, finding the median of an unordered list consists of sorting the list first to directly retrieve the median value, which is in the middle of the list! We see that the goal is to find the most obvious transformation.
- Using Graphs
Many problems, including the game of chess, can be solved by modeling it as a graph. Graph research algorithms are used. These include search and backtracking algorithms.
- Probabilistic and heuristic
- Probabilistic
They make random choices. - Genetic
Seeks a solution to the problem by mimicking biological evolutionary processes, with successive generations that are intermediate solutions. In fact, this repeats the principle of survival of the strongest. - Heuristics
The goal is not to find an optimal solution, but a good solution if the best would require too much time or resources.
- Probabilistic
Classification by complexity
Some algorithms complete in linear time, others require exponential time, and still others never complete.
Algorithms