Metraipolis › archive › dc_f5861087dbb2

Computational complexity — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Computational_complexity
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T23:03:59.414Z
SHA-256 of the archived text
de5898af26360a29fb8c19fa98a54ab7ee3c9c8ec1d5420e8b235cbc1ae66714
Stable URL of this page
https://metraipolis.com/documento/dc_f5861087dbb2

How to cite

Computational complexity — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Computational_complexity (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_f5861087dbb2 (Metraipolis archive dc_f5861087dbb2, sha256 de5898af26360a29fb8c19fa98a54ab7ee3c9c8ec1d5420e8b235cbc1ae66714)
BibTeX
@misc{dcf5861087dbb2,
  title = {Computational complexity — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Computational_complexity},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_f5861087dbb2; sha256 de5898af26360a29fb8c19fa98a54ab7ee3c9c8ec1d5420e8b235cbc1ae66714},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Computational_complexity. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: fisica e astronomia (deposito sistematico; ricerca «quantum computing»).
Fonte: Wikipedia in inglese, voce «Computational complexity» — https://en.wikipedia.org/wiki/Computational_complexity
Wikidata Q5157286 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5157286
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Computational_complexity?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1378898911, consultata il 2026-10-07T22:42:23.627Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 7f254009a1f43d89f3741a802e800c7151549c4ebbe22b119817f607157dce79