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:
“Cubism had been an analysis of the object and an attempt to put it before us in its totality; both as analysis and as synthesis, it was a criticism of appearance. Surrealism transmuted the object, and suddenly a canvas became an apparition: a new figuration, a real transfiguration.”
—Octavio Paz (b. 1914)