Computationally Inexpensive Algorithm

From GM-RKB
(Redirected from Efficient Algorithm)
Jump to: navigation, search

A Computationally Expensive Algorithm is an algorithm that requires a small number of steps to complete relative to its task input size.



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."