Content deleted Content added
m add references |
m Added 1 {{Bare URL PDF}} tag(s) using a script. For other recently-tagged pages with bare URLs, see Category:Articles with bare URLs for citations from August 2024 and Category:Articles with PDF format bare URLs for citations |
||
Line 1:
{{Short description|Amount of resources to perform an algorithm}}
{{no footnotes|date=December 2017}}
In [[computer science]], the '''computational complexity''' or simply '''complexity''' of an [[algorithm]] is the amount of resources required to run it.<ref>https://people.seas.harvard.edu/~salil/research/ComputationalComplexity-2ndEd.pdf {{Bare URL PDF|date=August 2024}}</ref> Particular focus is given to [[time complexity|computation time]] (generally measured by the number of needed elementary operations) and [[space complexity|memory storage]] requirements. The complexity of a [[computational problem|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 lower than the complexity of the most efficient known algorithms. Therefore, there is a large overlap between analysis of algorithms and complexity theory.
| |||