In analysis of algorithms, probabilistic analysis of algorithms is an approach to estimate the computational complexity of an algorithm or a computational problem. It starts from an assumption about a probabilistic distribution of the set of all possible inputs. This assumption is then used to design an efficient algorithm or to derive the complexity of a known algorithm. This approach is not the same as that of probabilistic algorithms, but the two may be combined.
For non-probabilistic, more specifically deterministic, algorithms, the most common types of complexity estimates are the average-case complexity and the almost-always complexity. To obtain the average-case complexity, given an input distribution, the expected time of an algorithm is evaluated, whereas for the almost-always complexity estimate, it is evaluated that the algorithm admits a given complexity estimate that almost surely holds.
In probabilistic analysis of probabilistic (randomized) algorithms, the distributions or average of all possible choices in randomized steps is also taken into account, in addition to the input distributions.
probabilistic, analysis, algorithms, this, article, does, cite, sources, please, help, improve, this, article, adding, citations, reliable, sources, unsourced, material, challenged, removed, find, sources, news, newspapers, books, scholar, jstor, april, 2021, . This article does not cite any sources Please help improve this article by adding citations to reliable sources Unsourced material may be challenged and removed Find sources Probabilistic analysis of algorithms news newspapers books scholar JSTOR April 2021 Learn how and when to remove this template message In analysis of algorithms probabilistic analysis of algorithms is an approach to estimate the computational complexity of an algorithm or a computational problem It starts from an assumption about a probabilistic distribution of the set of all possible inputs This assumption is then used to design an efficient algorithm or to derive the complexity of a known algorithm This approach is not the same as that of probabilistic algorithms but the two may be combined For non probabilistic more specifically deterministic algorithms the most common types of complexity estimates are the average case complexity and the almost always complexity To obtain the average case complexity given an input distribution the expected time of an algorithm is evaluated whereas for the almost always complexity estimate it is evaluated that the algorithm admits a given complexity estimate that almost surely holds In probabilistic analysis of probabilistic randomized algorithms the distributions or average of all possible choices in randomized steps is also taken into account in addition to the input distributions See also EditAmortized analysis Average case complexity Best worst and average case Random self reducibility Principle of deferred decision This algorithms or data structures related article is a stub You can help Wikipedia by expanding it vte Retrieved from https en wikipedia org w index php title Probabilistic analysis of algorithms amp oldid 1020332354, wikipedia, wiki, book, books, library,
