Computationally Inexpensive Algorithm
From GM-RKB
(Redirected from Efficient Algorithm)
A Computationally Expensive Algorithm is an algorithm that requires a small number of steps to complete relative to its task input size.
- AKA: Efficient Algorithm.
- Context:
- It can (typically) have a Low Computational Complexity.
- Counter-Example(s):
- See: P Task, Computational Complexity Theory, Polynomial-time Algorithm, Constant-time Algorithm.
References
2009
- (Fortnow, 2009) ⇒ Lance Fortnow. (2009). “The status of the P versus NP problem." In: Communications of the ACM, 52(9).
- In 1965, Jack Edmonds12 gave an efficient algorithm to solve this matching problem and suggested a formal definition of “efficient computation” (runs in time a fixed polynomial of the input size). The class of problems with efficient solutions would later become known as P for "Polynomial Time."