Randomized algorithm
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.
- Comment
- enA 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.
- Depiction
- DifferentFrom
- Algorithmic randomness
- Has abstract
- enA 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. One has to distinguish 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.
- Hypernym
- Algorithm
- Is primary topic of
- Randomized algorithm
- Label
- enRandomized algorithm
- Link from a Wikipage to an external page
- www.springer.com/de/book/9783642551970
- portal.acm.org/citation.cfm%3Fid=234313.234327
- Link from a Wikipage to another Wikipage
- AKS primality test
- Algorithm
- Analysis of algorithms
- Approximate counting algorithm
- Array data structure
- Atlantic City algorithm
- Attacker
- Big O notation
- Big Theta notation
- Bogosort
- Bounded-error probabilistic polynomial
- Category:Analysis of algorithms
- Category:Randomized algorithms
- Charles E. Leiserson
- Chemical reaction network
- Clifford Stein
- Communication complexity
- Competitive analysis (online algorithm)
- Complexity class
- Computational complexity theory
- Computational geometry
- Computer software
- Conditional probability
- Convex hull
- Count–min sketch
- Cryptographically secure pseudo-random number generator
- Cryptography
- Cut (graph theory)
- Cyber-physical system
- Decision problem
- Delaunay triangulation
- Deterministic algorithm
- Discrepancy theory
- Disperser
- Edge contraction
- Eli Upfal
- Embedded systems
- Éva Tardos
- Expander graph
- File:Contraction vertices.jpg
- File:Single run of Karger’s Mincut algorithm.svg
- Graph theory
- HyperLogLog
- Imre Bárány
- Introduction to Algorithms
- IP (complexity)
- Jon Kleinberg
- Karger's algorithm
- Las Vegas algorithm
- Markov's inequality
- Method of conditional probabilities
- Michael Mitzenmacher
- Miller–Rabin primality test
- Minimum feedback arc set
- Monte Carlo algorithm
- Monte Carlo method
- NP (complexity)
- Number theory
- P (complexity)
- Pairwise independence
- Pessimistic estimator
- Pocklington's algorithm
- Polynomial time
- Primality test
- Prime number
- Primitive recursive
- Principle of deferred decision
- Prisoner's dilemma
- Probabilistic analysis of algorithms
- Probabilistic roadmap
- Probabilistic Turing machine
- Pseudorandom
- Pseudorandom number generator
- PSPACE
- Quantum computer
- Quicksort
- Rajeev Motwani
- Random
- Random-access machine
- Randomized algorithms as zero-sum games
- Randomized incremental construction
- Randomness
- Robert M. Solovay
- Ronald L. Rivest
- RP (complexity)
- Solovay–Strassen primality test
- Square root
- Thomas H. Cormen
- Turing machine
- Uniform distribution (discrete)
- Universal hashing
- Volker Strassen
- Worst-case complexity
- Zoltán Füredi
- ZPP (complexity)
- SameAs
- 4mPpa
- Algorisme probabilístic
- Algorithme probabiliste
- Algoritmo probabilista
- Algoritmo probabilístico
- Algoritmo randomizzato
- Algorytm probabilistyczny
- Hazardigita algoritmo
- m.02hb1k
- Pravděpodobnostní algoritmus
- Q583461
- Randomisierter Algorithmus
- Randomized algorithm
- Randomizirani algoritam
- Вероятностный алгоритм
- Увипадковлений алгоритм
- אלגוריתם אקראי
- الگوریتمهای تصادفی
- خوارزمية عشوائية
- সম্ভাবনাভিত্তিক অ্যালগোরিদম
- ขั้นตอนวิธีแบบสุ่ม
- 乱択アルゴリズム
- 随机化算法
- 확률적 알고리즘
- Subject
- Category:Analysis of algorithms
- Category:Randomized algorithms
- Thumbnail
- WasDerivedFrom
- Randomized algorithm?oldid=1083506589&ns=0
- WikiPageLength
- 26736
- Wikipage page ID
- 495383
- Wikipage revision ID
- 1083506589
- WikiPageUsesTemplate
- Template:Abs
- Template:Citation
- Template:Cite journal
- Template:Distinguish-redirect
- Template:Isbn
- Template:Main
- Template:Math
- Template:Math proof
- Template:Math theorem
- Template:Mset
- Template:Mvar
- Template:Probabilistic
- Template:Reflist
- Template:Short description
- Template:Tmath
