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, for deterministic algorithms, the most common types of complexity estimates are
- the average-case complexity (expected time complexity), in which given an input distribution, the expected time of an algorithm is evaluated
- the almost always complexity estimates, in which given an input distribution, it is evaluated that the algorithm admits a given complexity estimate that almost surely holds.
Read more about Probabilistic Analysis Of Algorithms: Probabilistic Algorithms, See Also
Famous quotes containing the word analysis:
“A commodity appears at first sight an extremely obvious, trivial thing. But its analysis brings out that it is a very strange thing, abounding in metaphysical subtleties and theological niceties.”
—Karl Marx (18181883)