Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Average-case_complexity> ?p ?o }
Showing triples 1 to 66 of
66
with 100 triples per page.
- Average-case_complexity abstract "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.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 based 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.".
- Average-case_complexity wikiPageExternalLink average.ps.
- Average-case_complexity wikiPageExternalLink TR1995-711.pdf.
- Average-case_complexity wikiPageExternalLink 76.pdf.
- Average-case_complexity wikiPageExternalLink theta.html.
- Average-case_complexity wikiPageID "15383952".
- Average-case_complexity wikiPageLength "19596".
- Average-case_complexity wikiPageOutDegree "32".
- Average-case_complexity wikiPageRevisionID "677131761".
- Average-case_complexity wikiPageWikiLink Algorithm.
- Average-case_complexity wikiPageWikiLink Art_of_Computer_Programming.
- Average-case_complexity wikiPageWikiLink Association_for_Computing_Machinery.
- Average-case_complexity wikiPageWikiLink Category:Probabilistic_complexity_theory.
- Average-case_complexity wikiPageWikiLink Co-NP.
- Average-case_complexity wikiPageWikiLink CoNP.
- Average-case_complexity wikiPageWikiLink Computational_complexity_theory.
- Average-case_complexity wikiPageWikiLink Cryptography.
- Average-case_complexity wikiPageWikiLink Derandomization.
- Average-case_complexity wikiPageWikiLink Discrete_log.
- Average-case_complexity wikiPageWikiLink Discrete_logarithm.
- Average-case_complexity wikiPageWikiLink Donald_Knuth.
- Average-case_complexity wikiPageWikiLink EXP.
- Average-case_complexity wikiPageWikiLink EXPTIME.
- Average-case_complexity wikiPageWikiLink Hamiltonian_path_problem.
- Average-case_complexity wikiPageWikiLink Integer_factorization.
- Average-case_complexity wikiPageWikiLink Leonid_Levin.
- Average-case_complexity wikiPageWikiLink NEXP.
- Average-case_complexity wikiPageWikiLink NEXPTIME.
- Average-case_complexity wikiPageWikiLink NP-complete.
- Average-case_complexity wikiPageWikiLink NP-complete_problems.
- Average-case_complexity wikiPageWikiLink NP-completeness.
- Average-case_complexity wikiPageWikiLink NP_(complexity).
- Average-case_complexity wikiPageWikiLink Non-deterministic_Turing_machine.
- Average-case_complexity wikiPageWikiLink One-way_function.
- Average-case_complexity wikiPageWikiLink One-way_functions.
- Average-case_complexity wikiPageWikiLink P_(complexity).
- Average-case_complexity wikiPageWikiLink Probabilistic_analysis_of_algorithms.
- Average-case_complexity wikiPageWikiLink Probability_distribution.
- Average-case_complexity wikiPageWikiLink Quicksort.
- Average-case_complexity wikiPageWikiLink Randomized_algorithm.
- Average-case_complexity wikiPageWikiLink Symposium_on_Theory_of_Computing.
- Average-case_complexity wikiPageWikiLink The_Art_of_Computer_Programming.
- Average-case_complexity wikiPageWikiLink University_of_California,_San_Diego.
- Average-case_complexity wikiPageWikiLink Worst-case_complexity.
- Average-case_complexity wikiPageWikiLinkText "Average-case complexity".
- Average-case_complexity wikiPageWikiLinkText "average case".
- Average-case_complexity wikiPageWikiLinkText "average-case complexity".
- Average-case_complexity wikiPageWikiLinkText "expected cost".
- Average-case_complexity wikiPageWikiLinkText "on average".
- Average-case_complexity hasPhotoCollection Average-case_complexity.
- Average-case_complexity wikiPageUsesTemplate Template:Citation.
- Average-case_complexity wikiPageUsesTemplate Template:Reflist.
- Average-case_complexity wikiPageUsesTemplate Template:Rp.
- Average-case_complexity subject Category:Probabilistic_complexity_theory.
- Average-case_complexity hypernym Amount.
- Average-case_complexity type Disease.
- Average-case_complexity comment "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.There are three primary motivations for studying average-case complexity.".
- Average-case_complexity label "Average-case complexity".
- Average-case_complexity sameAs Complexité_en_moyenne_des_algorithmes.
- Average-case_complexity sameAs Complexidade_de_caso_médio.
- Average-case_complexity sameAs m.04gg5fk.
- Average-case_complexity sameAs Сложеност_просечног_случаја.
- Average-case_complexity sameAs Q4828244.
- Average-case_complexity sameAs Q4828244.
- Average-case_complexity wasDerivedFrom Average-case_complexity?oldid=677131761.
- Average-case_complexity isPrimaryTopicOf Average-case_complexity.