- Probabilistic analysis of algorithms
analysis of algorithms, probabilistic analysis of algorithms is an approach to estimate the computational complexityof an algorithmor 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
average-case complexity(expected time complexity), in which given an input distribution, the expectedtime 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
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.
Best, worst and average case
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