Probabilistic analysis of algorithms
- Probabilistic analysis of algorithms
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 algorithms.
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.
In probabilistic analysis of probabilistic (randomized) algorithms, the distributions or averaging for all possible choices in randomized steps are also taken into an account, in addition to the input distributions.
ee also
*Amortized analysis
*Average-case complexity
*Best, worst and average case
*Random self-reducibility
Wikimedia Foundation.
2010.
Look at other dictionaries:
Amortized analysis — In computer science, especially analysis of algorithms, amortized analysis refers to finding the average running time per operation over a worst case sequence of operations. Amortized analysis differs from average case performance in that… … Wikipedia
Construction and Analysis of Distributed Processes — Developer(s) the INRIA VASY team Initial release 1986, 24–25 years ago Stable release … Wikipedia
Principal component analysis — PCA of a multivariate Gaussian distribution centered at (1,3) with a standard deviation of 3 in roughly the (0.878, 0.478) direction and of 1 in the orthogonal direction. The vectors shown are the eigenvectors of the covariance matrix scaled by… … Wikipedia
Decision analysis — (DA) is the discipline comprising the philosophy, theory, methodology, and professional practice necessary to address important decisions in a formal manner. Decision analysis includes many procedures, methods, and tools for identifying, clearly… … Wikipedia
Dynamic network analysis — (DNA) is an emergent scientific field that brings together traditional social network analysis (SNA), link analysis (LA) and multi agent systems (MAS) within network science and network theory. There are two aspects of this field. The first is… … Wikipedia
List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… … Wikipedia
List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… … Wikipedia
Boolean analysis — was introduced by Flament (1976). The goal of a Boolean analysis is to detect deterministic dependencies between the items of a questionnaire in observed response patterns. These deterministic dependencies have the form of logical formulas… … Wikipedia
Statistical static timing analysis — Conventional static timing analysis (STA) has been a stock analysis algorithm for the design of digital circuits over the last 30 years. However, in recent years the increased variation in semiconductor devices and interconnect has introduced a… … Wikipedia
Randomized algorithm — Part of a series on Probabilistic data structures Bloom filter · Skip list … Wikipedia
