Average-case complexity (original) (raw)
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.
| Property | Value |
|---|---|
| dbo: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 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. (en) La complexité en moyenne d'un algorithme est la quantité d'une ressource donnée, typiquement le temps, utilisée par l'algorithme lors de son exécution pour traiter une entrée tirée selon une distribution donnée. Il s'agit par conséquent d'une moyenne de la complexité, pondérée entre les différentes entrées possibles selon la distribution choisie. Le plus souvent, on ne précise pas la distribution et on utilise implicitement une distribution uniforme (i.e. une loi uniforme discrète dans le cas discret), c'est-à-dire que toutes les entrées sont considérées comme équiprobables. C'est une mesure importante pour l'analyse de la complexité des algorithmes, et elle s'oppose à la complexité dans le pire des cas qui considère la complexité maximale de l'algorithme sur toutes les entrées possibles. (fr) Em teoria de complexidade computacional, a complexidade de caso médio de um algoritmo é a quantidade de algum recurso computacional (tipicamente tempo) utilizado pelo algoritmo, numa média sobre todas as entradas possíveis. É frequentemente contrastada com a complexidade de pior caso que considera a complexidade máxima do algoritmo sobre todas as entradas possíveis. Existem três motivações principais para estudar a complexidade de caso médio. Primeiramente, apesar de alguns problemas serem intratáveis no pior caso, as entradas que elicitam esse comportamento podem raramente ocorrer na prática, e portanto a complexidade de caso médio pode ser uma medida mais precisa da performance de um algoritmo. Segundo, a análise de complexidade de caso médio fornece ferramentas e técnicas para gerar instâncias difíceis de problemas que podem ser utilizadas em áreas como criptografia e probabilidade algorítmica. Terceiro, complexidade de caso médio permite diferenciar o algoritmo mais eficiente na prática entre algoritmos equivalentes em complexidade (por exemplo, quicksort). A análise de caso médio requer uma noção de uma entrada "média" para um algoritmo, o que leva ao problema de conceber uma distribuição de probabilidade sobre as entradas. Alternativamente, um algoritmo probabilístico pode ser usado. A análise de tais algoritmos leva à noção relacionada de uma complexidade esperada. (pt) В теории вычислительной сложности сложность алгоритма в среднем — это количество неких вычислительных ресурсов (обычно — время), требуемое для работы алгоритма, усреднённое по всем возможным входным данным. Понятие часто противопоставляется , где рассматривается максимальная сложность алгоритма по всем входным данным. Имеются три основных причины изучения сложности в среднем. Во-первых, хотя некоторые задачи могут быть трудно разрешимы в худшем случае, входные данные, которые приводят к такому поведению, на практике встречаются редко, так что сложность в среднем может оказаться более аккуратной мерой производительности алгоритма. Во-вторых, анализ сложности в среднем даёт средства и технику генерации сложных данных для задачи, что можно использовать в криптографии и . В-третьих, сложность в среднем позволяет выделить наиболее эффективный алгоритм на практике среди алгоритмов той же основной сложности (например, быстрая сортировка). Анализ алгоритмов в среднем требует понятия «средних» данных алгоритма, что приводит к задаче продумывания распределения вероятностей входных данных. Может быть использован также вероятностный алгоритм. Анализ таких алгоритмов приводит к связанному понятию ожидаемой сложности. (ru) |
| dbo:wikiPageExternalLink | http://www-cse.ucsd.edu/~russell/average.ps http://research.microsoft.com/~gurevich/Opera/76.pdf http://www.cs.nyu.edu/csweb/Research/TechReports/TR1995-711/TR1995-711.pdf https://web.archive.org/web/20090214175940/http:/www.itl.nist.gov/div897/sqg/dads/HTML/theta.html |
| dbo:wikiPageID | 15383952 (xsd:integer) |
| dbo:wikiPageLength | 19914 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1073706948 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Probability_distribution dbr:Quicksort dbr:NP_(complexity) dbr:Probabilistic_analysis_of_algorithms dbr:Algorithm dbc:Randomized_algorithms dbr:Best,_worst_and_average_case dbr:University_of_California,_San_Diego dbr:Derandomization dbr:Integer_factorization dbr:Worst-case_complexity dbr:Cryptography dbr:One-way_functions dbr:NP-complete dbr:Leonid_Levin dbr:Computational_complexity_theory dbr:CoNP dbr:Hamiltonian_path_problem dbr:P_(complexity) dbr:Amortized_analysis dbr:Non-deterministic_Turing_machine dbr:Association_for_Computing_Machinery dbr:Donald_Knuth dbr:Randomized_algorithm dbr:Symposium_on_Theory_of_Computing dbr:NP-complete_problems dbr:Art_of_Computer_Programming dbr:Discrete_log dbr:NEXP dbr:EXP |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Redirect dbt:Reflist dbt:Rp |
| dct:subject | dbc:Randomized_algorithms |
| gold:hypernym | dbr:Amount |
| rdf:type | dbo:Disease |
| rdfs: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. (en) La complexité en moyenne d'un algorithme est la quantité d'une ressource donnée, typiquement le temps, utilisée par l'algorithme lors de son exécution pour traiter une entrée tirée selon une distribution donnée. Il s'agit par conséquent d'une moyenne de la complexité, pondérée entre les différentes entrées possibles selon la distribution choisie. Le plus souvent, on ne précise pas la distribution et on utilise implicitement une distribution uniforme (i.e. une loi uniforme discrète dans le cas discret), c'est-à-dire que toutes les entrées sont considérées comme équiprobables. (fr) Em teoria de complexidade computacional, a complexidade de caso médio de um algoritmo é a quantidade de algum recurso computacional (tipicamente tempo) utilizado pelo algoritmo, numa média sobre todas as entradas possíveis. É frequentemente contrastada com a complexidade de pior caso que considera a complexidade máxima do algoritmo sobre todas as entradas possíveis. (pt) В теории вычислительной сложности сложность алгоритма в среднем — это количество неких вычислительных ресурсов (обычно — время), требуемое для работы алгоритма, усреднённое по всем возможным входным данным. Понятие часто противопоставляется , где рассматривается максимальная сложность алгоритма по всем входным данным. Анализ алгоритмов в среднем требует понятия «средних» данных алгоритма, что приводит к задаче продумывания распределения вероятностей входных данных. Может быть использован также вероятностный алгоритм. Анализ таких алгоритмов приводит к связанному понятию ожидаемой сложности. (ru) |
| rdfs:label | Average-case complexity (en) Complexité en moyenne des algorithmes (fr) Complexidade de caso médio (pt) Сложность алгоритма в среднем (ru) |
| owl:sameAs | freebase:Average-case complexity yago-res:Average-case complexity wikidata:Average-case complexity dbpedia-fa:Average-case complexity dbpedia-fr:Average-case complexity dbpedia-pt:Average-case complexity dbpedia-ru:Average-case complexity dbpedia-sr:Average-case complexity https://global.dbpedia.org/id/4UDN4 |
| prov:wasDerivedFrom | wikipedia-en:Average-case_complexity?oldid=1073706948&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Average-case_complexity |
| is dbo:knownFor of | dbr:Leonid_Levin |
| is dbo:wikiPageRedirects of | dbr:AvgP dbr:DistNP dbr:DistP dbr:Average_case_complexity dbr:Average_case_computational_complexity dbr:Expected_time |
| is dbo:wikiPageWikiLink of | dbr:Probabilistic_analysis_of_algorithms dbr:Boyer–Moore–Horspool_algorithm dbr:Best,_worst_and_average_case dbr:Cycle_detection dbr:Indistinguishability_obfuscation dbr:Worst-case_complexity dbr:Criss-cross_algorithm dbr:Generic-case_complexity dbr:Random_self-reducibility dbr:Leonid_Levin dbr:Computational_complexity dbr:Computational_hardness_assumption dbr:Harmonic_series_(mathematics) dbr:AvgP dbr:Time_complexity dbr:Lattice-based_cryptography dbr:Lattice_problem dbr:Security_of_cryptographic_hash_functions dbr:Amortized_analysis dbr:DFA_minimization dbr:Partial_sorting dbr:Discrete_logarithm dbr:Isolation_lemma dbr:AVGP_(disambiguation) dbr:Hash_table dbr:Jeffrey_Vitter dbr:Smoothed_analysis dbr:DistNP dbr:DistP dbr:Philippe_Flajolet dbr:Circuit_complexity dbr:Klee–Minty_cube dbr:P_versus_NP_problem dbr:Skip_list dbr:Average_case_complexity dbr:Average_case_computational_complexity dbr:Expected_time |
| is dbp:knownFor of | dbr:Leonid_Levin |
| is foaf:primaryTopic of | wikipedia-en:Average-case_complexity |