Revision as of 09:04, 23 February 2021 edit D.Lazard (talk \| contribs) Extended confirmed users 35,614 edits Undid revision 1008392505 by DonAByrd (talk) and use "low" instead ← Previous edit		Revision as of 11:41, 23 February 2021 edit undo BercherP (talk \| contribs) 11 edits The introdcution makes now clear that "computational complexity" does normally NOT refer to the complexity of an algorithm (although this is what the article is about^^), but to that of a problem. For that, the last parapgraph was fused with the first, to explain that more clearly. Anyway, the current title of the article is therefore a bit misleading, since computational complexity does ALMSOT NEVER refer to the complexity of algorithms, but to that of problems. So it needs to be renamed. Tag: Reverted Next edit →
Line 1: {{Short description\|amount of resources (usually time and/or memory) 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. Particular focus is given to [[time complexity\|time]] and [[space complexity\|memory]] requirements. The study of the complexity of explicitly given algorithms is called [[analysis of algorithms]]. This is fundamentally different from the study of the complexity of [[computational problem\|problems]], which is called [[computational complexity theory]]. Most of the time, '''computational complexity''' refers to the computational complexity of solving a problem and not to the complexity of an algorithm, but both terminologies are used. 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. 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 {{math\|''n'' → ''f''(''n'')}}, where {{math\|''n''}} is the size of the input and {{math\|''f''(''n'')}} is either the [[worst-case complexity]] (the maximum of the amount of resources that are needed over all inputs of size {{math\|''n''}}) or the [[average-case complexity]] (the average of the amount of resources over all inputs of size {{math\|''n''}}). [[Time complexity]] is generally expressed as the number of required elementary operations on an input of size {{math\|''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 [[computer memory\|memory]] required by an algorithm on an input of size {{math\|''n''}}. The study of the complexity of explicitly given algorithms is called [[analysis of algorithms]], while the study of the complexity of [[computational problem\|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. ==Resources==

Computational complexity: Difference between revisions