In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems. Algorithms can perform calculation, data processing and automated reasoning tasks.
As an effective method, an algorithm 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.
The concept of algorithm has existed for centuries. Greek mathematicians used algorithms in, for example, the sieve of Eratosthenes for finding prime numbers and the Euclidean algorithm for finding the greatest common divisor of two numbers.
The word algorithm itself derives from the 9th Century mathematician Muḥammad ibn Mūsā al-Khwārizmī. A partial formalization of what would become the modern concept of algorithm began with attempts to solve the Entscheidungsproblem (decision problem) posed by David Hilbert in 1928. Later formalizations were framed as attempts to define “effective calculability” or “effective method”. Those formalizations included the Gödel–Herbrand–Kleene recursive functions of 1930, 1934 and 1935, Alonzo Church’s lambda calculus of 1936, Emil Post’s Formulation 1 of 1936, and Alan Turing’s Turing machines of 1936–37 and 1939.
Design
Algorithm design refers to a method or mathematical process for problem solving and engineering algorithms. The design of algorithms is part of many solution theories of operation research, such as dynamic programming and divide-and-conquer. Techniques for designing and implementing algorithm designs are also called algorithm design patterns, such as the template method pattern and decorator pattern.
One of the most important aspects of algorithm design is creating an algorithm that has an efficient run-time, also known as its Big O.
Typical steps in development of algorithms:
- Problem definition
- Development of a model
- Specification of algorithm
- Designing an algorithm
- Checking the correctness of algorithm
- Analysis of algorithm
- Implementation of algorithm
- Program testing
- Documentation preparation
Example
One of the simplest algorithms is to find the largest number in a list of numbers of random order. Finding the solution requires looking at every number in the list. From this follows a simple algorithm, which can be stated in a high-level description English prose, as:
High-level description:
- If there are no numbers in the set then there is no highest number.
- Assume the first number in the set is the largest number in the set.
- For each remaining number in the set: if this number is larger than the current largest number, consider this number to be the largest number in the set.
- When there are no numbers left in the set to iterate over, consider the current largest number to be the largest number of the set.
Algorithmic Analysis
It is frequently important to know how much of a particular resource (such as time or storage) is theoretically required for a given algorithm. Methods have been developed for the analysis of algorithms to obtain such quantitative answers (estimates).
Classification
There are various ways to classify algorithms:
By implementation
- Recursion
- Logical
- Serial, parallel or distributed
- Deterministic or non-deterministic
- Exact or approximate
- Quantum algorithm
By design paradigm
- Brute-force or exhaustive search
- Divide and conquer
- Search and enumeration
- Randomized algorithm
- Reduction of complexity
- Back tracking
Optimization problems
- Linear programming
- Dynamic programming
- The greedy method
- The heuristic method
By field of study
Every field of science has its own problems and needs efficient algorithms. Related problems in one field are often studied together. Some example classes are search algorithms, sorting algorithms, merge algorithms, numerical algorithms, graph algorithms, string algorithms, computational geometric algorithms, combinatorial algorithms, medical algorithms, machine learning, cryptography, data compression algorithms and parsing techniques.
By complexity
Algorithms can be classified by the amount of time they need to complete compared to their input size:
- Constant time
- Linear time
- Logarithmic time
- Polynomial time
- Exponential time