In mathematics and computing, an algorithm is a finite sequence of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. Informally, the concept of an algorithm is often illustrated by the example of a recipe, albeit more complex. Algorithms often contain steps that repeat (iterate) or require decisions, such as by using logic or comparisons.
Algorithms constitute a foundational concept in computer science. In most higher-level computer programs, algorithms act in complex patterns, each using smaller and smaller sub-methods, which are built up to the program as a whole. In other words, a computer program may be regarded as an algorithm that has nested sets of smaller algorithms within it. Most algorithms can be directly implemented by computer programs; any other algorithms can at least in theory be simulated by computer programs.
As early as 1600 B.C.E., the Babylonians developed algorithms for factorization and finding square roots of numbers. The Euclidean algorithm, given in Euclid's Elements around 300 B.C.E., was useful for determining the greatest common divisor of two integers, among other things. The latter algorithm was probably not discovered by Euclid and may have been known by the Greeks up to 200 years earlier.
Between CE 813 and 833, Persian mathematician Al-Khawarizmi (Abu Ja'afar Abdullah Muhammad Ibn Mūsā al-Khawārizmī) described a procedure for solving linear equations and quadratic equations. The word "algorithm," used for such a procedure, comes from his name.
Initially, the term "algorism" was used to refer to the rules of performing arithmetic computations with Hindu-Arabic numerals. Later, based on European Latin translations of al-Khwarizmi's name, the word evolved into "algoritmi" and then "algorithm" by the eighteenth century. The meaning of the word was also broadened to include all definite mathematical procedures for solving problems or performing tasks.
The lack of mathematical rigor in the "well-defined procedure" definition of algorithms posed some difficulties for mathematicians and logicians of the nineteenth and early twentieth centuries. Their understanding of algorithms, however, was greatly improved in 1936, with Alan Turing's description of the "Turing machine" (an abstract model of a computer), and the assertion that all possible calculations can be emulated on a Turing machine—a statement known as the "Church-Turing thesis," which has so far not been contradicted. Currently, a formal criterion for an algorithm is that it is a procedure that can be implemented on a completely specified Turing machine or equivalent formalism. In this manner, the concept of an algorithm has become a foundation for the development of computer science.
The first case of an algorithm written for a computer occurs in Ada Lovelace's notes on Charles Babbage's analytical engine, written in 1842. For that, she is considered by many to be the world's first programmer. Babbage, however, never completed his analytical engine, and the algorithm was never implemented on it.
Algorithms are essential to the way computers process information. A computer program is basically an algorithm that tells the computer what specific steps to perform, and in what order, to carry out a specified task. The task could be something like calculating employees’ paychecks or printing students’ report cards. In formal terms, an algorithm can be considered to be any sequence of operations that can be performed by a "Turing-complete" system—that is, a programming language that has a computational power equivalent to a universal Turing machine.
Typically, when an algorithm is associated with processing information, data is read from an input source or device, written to an output sink or device, and stored for further processing. Such data is stored in a data structure (a tool for efficiently storing data in a computer), and a predefined set of operations may be performed on it based on the demands of the algorithm.
For any such computational process, an algorithm must be rigorously defined—that is, specified in a way that applies to all possible circumstances. In other words, it must be able to deal with any possible discrepancy, error, or alternative situation occurring during the computation. For example, it needs to be able to deal with an invalid input, such as a letter instead of a number.
Algorithms generally execute their operations in sequential order: From top to bottom, and left to right. Occasionally, however, certain control structures (such as loops) can alter the order in which a particular segment of the program is conducted.
A computer program may be regarded as an algorithm that has a set of smaller algorithms within it, and each of these may contain additional subsets of algorithms. This design is called "top-down design," where each level of abstraction (from the main algorithm to the sub-algorithms and so on) increases in specificity and detail. To illustrate, each sub-algorithm is designed to complete a specific task, and the main algorithm brings the results of these tasks together to generate a solution (or output) for the computational problem.
This type of formalization of an algorithm is based on the premises of "imperative programming"—a formalism that describes a task in discrete, "mechanical" terms. Unique to this concept of formalized algorithms is the "assignment operation," setting the value of a variable. It derives from the intuition of "memory" as a scratch pad. (Alternate concepts of an algorithm can be found in "functional programming" and "logic programming.")
Donald Knuth made a list of five properties that are still widely accepted as requirements for an algorithm:
An example of such an algorithm would be the Euclidean algorithm for determining the greatest common divisor of two natural numbers.
This description of an algorithm is intuitively clear but lacks formal rigor. Some terms—such as "precisely defined," "rigorously and unambiguously specified," or "sufficiently basic,"—are not exactly clear.
Thus the academically accepted definition of an algorithm stipulates a finite time frame of operation. Some, however, insist that the definition should include procedures that may run forever without stopping, arguing that some entity may be required to carry out such tasks. In such a case, the success of the algorithm needs to be redefined, to allow for output sequences that are unconstrained by time. For example, an algorithm that verifies if there are more zeros than ones in an infinite random binary sequence must run forever, to be effective. If implemented correctly, the algorithm's output will be useful. For as long as it examines the sequence, the algorithm gives a positive response when the number of examined zeros outnumber the ones, and a negative response otherwise. Success for this algorithm could then be defined as eventually producing only positive responses if the sequence has more zeros than ones, and producing mixtures of positive and negative responses in other cases.
Algorithms can be expressed in many types of notation, such as natural languages, pseudocode, flowcharts, and programming languages. Natural language expressions of algorithms tend to be verbose and ambiguous, and they are rarely used for complex or technical algorithms. Pseudocode and flowcharts are structured ways to express algorithms that avoid many of the ambiguities common in natural language statements, while avoiding implementation details. Programming languages are primarily intended for expressing algorithms in a form that can be executed by a computer, but they are often used as a way to define or document algorithms.
Most algorithms are intended to be implemented as computer programs. Many algorithms, however, are implemented by other means, such as a biological neural network—the human brain implementing arithmetic or an insect relocating food—or an electric circuit, or a mechanical device.
One of the simplest algorithms is to pick out the largest number from an unsorted list of numbers. The solution necessarily requires looking at every number in the list, but only once at each. From this follows a simple algorithm, which can be stated in English as follows:
Here is a more formal coding of the algorithm in pseudocode:
Input: A list of numbers L. Output: The largest number in the list L.
if L.size = 0 return null largest ← L for each item in L, do if item > largest, then largest ← item return largest
Below is a much simpler algorithm presented somewhat formally but still in English instead of pseudocode. It determines whether a given number n is even or odd:
A more complex example is Euclid's algorithm, which is one of the oldest algorithms.
As it happens, most people who implement algorithms want to know how much of a particular resource (such as time or storage) is required for a given algorithm. Methods have been developed for the analysis of algorithms to obtain such quantitative answers. For example, the above algorithm has a time requirement of O(n), using the big O notation with n as the length of the list. At all times, the algorithm needs to remember only two values: The largest number found so far, and its current position in the input list. Therefore it is said to have a space requirement of O(1) In this example the sizes of the numbers themselves could be unbounded and one could therefore argue that the space requirement is O(log n). In practice, however, the numbers considered would be bounded and hence the space taken up by each number is fixed. (Note that the size of the inputs is not counted as space used by the algorithm.)
Different algorithms may complete the same task with a different set of instructions in less or more time, space, or effort than others. For example, consider two different recipes for making a casserole: One is a frozen package and simply needs to be warmed up in the microwave; but the other spells out how to make a casserole from scratch and involves using a conventional oven. Both recipes end up with roughly the same dish, but each has a different time and space requirement.
The analysis and study of algorithms is a field within computer science and is often practiced abstractly (without the use of a specific programming language or other implementation). In this sense, it resembles other mathematical disciplines in that the analysis focuses on the underlying principles of the algorithm, not on any particular implementation. The pseudocode is simplest and abstract enough for such analysis.
There are various ways to classify algorithms, each with its own merits.
One way to classify algorithms is by implementation means.
Another way of classifying algorithms is by their design methodology or paradigm. There are a certain number of paradigms, each different from the other. Furthermore, each of these categories will include many different types of algorithms. Some commonly found paradigms include:
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, machine learning, cryptography, data compression algorithms, and parsing techniques.
Some of these fields overlap with each other and advancing in algorithms for one field causes advancement in many fields and sometimes completely unrelated fields. For example, dynamic programming is originally invented for optimization in resource consumption in industries, but it is used in solving a broad range of problems in many fields.
Some algorithms complete in linear time, some complete in an exponential amount of time, and some never complete. One problem may have multiple algorithms, and some problems may have no algorithms. Some problems have no known efficient algorithms. There are also mappings from some problems to other problems. So computer scientists found it is suitable to classify the problems rather than algorithms into equivalence classes based on their complexity.
All links retrieved March 5, 2016.
New World Encyclopedia writers and editors rewrote and completed the Wikipedia article in accordance with New World Encyclopedia standards. This article abides by terms of the Creative Commons CC-by-sa 3.0 License (CC-by-sa), which may be used and disseminated with proper attribution. Credit is due under the terms of this license that can reference both the New World Encyclopedia contributors and the selfless volunteer contributors of the Wikimedia Foundation. To cite this article click here for a list of acceptable citing formats.The history of earlier contributions by wikipedians is accessible to researchers here:
The history of this article since it was imported to New World Encyclopedia: