Metraipolis › archive › dc_db49bda7a1e5

Randomized algorithm — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Randomized_algorithm
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T21:35:54.260Z
SHA-256 of the archived text
cdb87ad08a933d0b39cd1380c79b96c954ce3439ab2b90870caca7129a7f7075
Stable URL of this page
https://metraipolis.com/documento/dc_db49bda7a1e5

How to cite

Randomized algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Randomized_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_db49bda7a1e5 (Metraipolis archive dc_db49bda7a1e5, sha256 cdb87ad08a933d0b39cd1380c79b96c954ce3439ab2b90870caca7129a7f7075)
BibTeX
@misc{dcdb49bda7a1e5,
  title = {Randomized algorithm — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Randomized_algorithm},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_db49bda7a1e5; sha256 cdb87ad08a933d0b39cd1380c79b96c954ce3439ab2b90870caca7129a7f7075},
  year = {2026}
}

Archived text

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

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables. There is a distinction between algorithms that use the random input so that they always terminate with the correct answer, but where the expected running time is finite (Las Vegas algorithms, for example Quicksort), and algorithms which have a chance of producing an incorrect result (Monte Carlo algorithms, for example the Monte Carlo algorithm for the MFAS problem) or fail to produce a result either by signaling a failure or failing to terminate. In some cases, probabilistic algorithms are the only practical means of solving a problem. In common practice, randomized algorithms are approximated using a pseudorandom number generator in place of a true source of random bits; such an implementation may deviate from the expected theoretical behavior and mathematical guarantees which may depend on the existence of an ideal true random number generator.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «combinatorics»).
Fonte: Wikipedia in inglese, voce «Randomized algorithm» — https://en.wikipedia.org/wiki/Randomized_algorithm
Wikidata Q583461 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q583461
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Randomized_algorithm?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 1375967533, consultata il 2026-10-07T21:06:56.355Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 56958bf9f5e0830da31c71c1b92a8dbbfbc0ac3371c0779d42fb3df3f7d1d5f6