Method
Computational complexity
Overview
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem.
The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory. Both areas are highly related, as the complexity of an algorithm is always an upper bound on the complexity of the problem solved by this algorithm. Moreover, for designing efficient algorithms, it is often fundamental to compare the complexity of a specific algorithm to the complexity of the problem to be solved. Also, in most cases, the only thing that is known about the complexity of a problem is that it is no higher than the complexity of the most efficient known algorithms. Therefore, there is a large overlap between analysis of algorithms and complexity theory.
As the amount of resources required to run an algorithm generally varies with the size of the input, the complexity is typically expressed as a function n ↦ f(n), where n is the size of the input and f(n) is either the worst-case complexity (the maximum of the amount of resources that are needed over all inputs of size n) or the average-case complexity (the average of the amount of resources over all inputs of size n). Time complexity is generally expressed as the number of required elementary operations on an input of size n, where elementary operations are assumed to take a constant amount of time on a given computer and change only by a constant factor when run on a different computer. Space complexity is generally expressed as the amount of memory required by an algorithm on an input of size n.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Possible passages
Found by search and not yet checked by a person; they may only mention the idea in passing.
In respect to any complex eternal object, _S(D1, D2, ... Dn)_, the eternal objects _D1, ... Dn_, whose individual essences are constitutive of the individual essence of _S(D1, ... Dn)_, are called the components of _S(D1, ... Dn)_. It is obvious that the grade of complexity to be ascribed to _S(D1, ... Dn)_ is to be taken as one above the highest grade of complexity to be found among its components.
Alfred North Whitehead, Science and the modern world
States what Computational complexity is.
It doubtless makes little difference whether a disease be attributed to big or little, black or red, demons or whether the cause be represented by a, b, or c, etc. But where data and hypotheses are such as are capable of verification, i.e., of mutually checking up each other, a change in one without a corresponding modification of the other is the principle of all formal fallacies.[18]
John Dewey, Creative Intelligence
States what Computational complexity is.
227.] Finite Cognition, when it pre-supposes what is distinguished from it to be something already existing and confronting it,--to be the various facts of external nature or of consciousness--has, in the first place, (1) Formal identity or the abstraction of universality for the form of its action. Its activity therefore consists in analysing the given concrete object, isolating its differences, and giving them the…
Georg Wilhelm Friedrich Hegel, The Logic of Hegel
States what Computational complexity is.
Philosophers who discussed Computational complexity
Related ideas
- Exponential growth
- Quantum mechanics
- Turing machine
- Bit
- Time complexity
- Combinatorics
- Computer science
- Complex number
- Algorithm
- Computer
- Computer memory
- Search algorithm
Place in the tradition
Part of First-order logic.