Average-case complexity
In computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted with worst-case complexity which considers the maximal complexity of the algorithm over all possible inputs.
- Comment
- enIn computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted with worst-case complexity which considers the maximal complexity of the algorithm over all possible inputs.
- Has abstract
- enIn computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted with worst-case complexity which considers the maximal complexity of the algorithm over all possible inputs. There are three primary motivations for studying average-case complexity. First, although some problems may be intractable in the worst-case, the inputs which elicit this behavior may rarely occur in practice, so the average-case complexity may be a more accurate measure of an algorithm's performance. Second, average-case complexity analysis provides tools and techniques to generate hard instances of problems which can be utilized in areas such as cryptography and derandomization. Third, average-case complexity allows discriminating the most efficient algorithm in practice among algorithms of equivalent best case complexity (for instance Quicksort). Average-case analysis requires a notion of an "average" input to an algorithm, which leads to the problem of devising a probability distribution over inputs. Alternatively, a randomized algorithm can be used. The analysis of such algorithms leads to the related notion of an expected complexity.
- Hypernym
- Amount
- Is primary topic of
- Average-case complexity
- Label
- enAverage-case complexity
- Link from a Wikipage to an external page
- research.microsoft.com/~gurevich/Opera/76.pdf
- www-cse.ucsd.edu/~russell/average.ps
- web.archive.org/web/20090214175940/http:/www.itl.nist.gov/div897/sqg/dads/HTML/theta.html
- www.cs.nyu.edu/csweb/Research/TechReports/TR1995-711/TR1995-711.pdf
- Link from a Wikipage to another Wikipage
- Algorithm
- Amortized analysis
- Art of Computer Programming
- Association for Computing Machinery
- Best, worst and average case
- Category:Randomized algorithms
- Computational complexity theory
- CoNP
- Cryptography
- Derandomization
- Discrete log
- Donald Knuth
- EXP
- Hamiltonian path problem
- Integer factorization
- Leonid Levin
- NEXP
- Non-deterministic Turing machine
- NP (complexity)
- NP-complete
- NP-complete problems
- One-way functions
- P (complexity)
- Probabilistic analysis of algorithms
- Probability distribution
- Quicksort
- Randomized algorithm
- Symposium on Theory of Computing
- University of California, San Diego
- Worst-case complexity
- SameAs
- 4UDN4
- Average-case complexity
- Complexidade de caso médio
- Complexité en moyenne des algorithmes
- m.04gg5fk
- Q4828244
- Сложеност просечног случаја
- Сложность алгоритма в среднем
- پیچیدگی حالت متوسط
- Subject
- Category:Randomized algorithms
- WasDerivedFrom
- Average-case complexity?oldid=1073706948&ns=0
- WikiPageLength
- 19914
- Wikipage page ID
- 15383952
- Wikipage revision ID
- 1073706948
- WikiPageUsesTemplate
- Template:Citation
- Template:Redirect
- Template:Reflist
- Template:Rp