| dbo:abstract |
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) |
| dbo:wikiPageExternalLink |
http://oai.cwi.nl/oai/asset/1991/1991A.pdf https://dx.doi.org/10.1561/0400000004 http://www.lifl.fr/~jdelahay/pls/111.pdf |
| dbo:wikiPageID |
8053055 (xsd:integer) |
| dbo:wikiPageLength |
5021 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
186972813 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbpedia-fr:Algorithme dbpedia-fr:Algorithme_de_tri dbpedia-fr:Analyse_de_la_complexité_des_algorithmes dbpedia-fr:Analyse_lisse_d'algorithme dbpedia-fr:Belin_éditeur category-fr:Algorithmique category-fr:Théorie_de_la_complexité_des_algorithmes dbpedia-fr:Complexité_dans_le_pire_des_cas dbpedia-fr:Complexité_de_Kolmogorov dbpedia-fr:Complexité_en_temps dbpedia-fr:Cryptographie dbpedia-fr:Loi_de_probabilité dbpedia-fr:Loi_uniforme_discrète dbpedia-fr:Luca_Trevisan dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) dbpedia-fr:Tri_fusion dbpedia-fr:Tri_par_insertion dbpedia-fr:Tri_rapide dbpedia-fr:Tri_à_peigne |
| prop-fr:année |
1992 (xsd:integer) 2003 (xsd:integer) 2006 (xsd:integer) |
| prop-fr:auteur |
dbpedia-fr:Luca_Trevisan Andrej Bogdanov (fr) |
| prop-fr:chapitre |
11 (xsd:integer) |
| prop-fr:jour |
25 (xsd:integer) |
| prop-fr:lireEnLigne |
http://oai.cwi.nl/oai/asset/1991/1991A.pdf http://www.lifl.fr/~jdelahay/pls/111.pdf |
| prop-fr:mois |
décembre (fr) mai (fr) |
| prop-fr:nom |
Li (fr) Delahaye (fr) Vitanyi (fr) |
| prop-fr:numéro |
1 (xsd:integer) |
| prop-fr:pages |
145 (xsd:integer) |
| prop-fr:passage |
1 (xsd:integer) |
| prop-fr:prénom |
Paul (fr) Jean-Paul (fr) Ming (fr) |
| prop-fr:périodique |
Pour la science (fr) Information Processing Letters (fr) Foundations and Trends® in Theoretical Computer Science (fr) |
| prop-fr:sousTitre |
Aux limites des mathématiques et de l'informatique (fr) |
| prop-fr:titre |
Average-Case Complexity (fr) Complexités (fr) La complexité mesurée… (fr) Average-case complexity under the universal distribution equals worst-case complexity (fr) |
| prop-fr:url |
https://dx.doi.org/10.1561/0400000004 |
| prop-fr:volume |
2 (xsd:integer) 42 (xsd:integer) |
| prop-fr:wikiPageUsesTemplate |
dbpedia-fr:Modèle:, dbpedia-fr:Modèle:Article dbpedia-fr:Modèle:En dbpedia-fr:Modèle:Ouvrage dbpedia-fr:Modèle:Portail dbpedia-fr:Modèle:Références dbpedia-fr:Modèle:Ébauche |
| prop-fr:éditeur |
dbpedia-fr:Belin_éditeur |
| dct:subject |
category-fr:Algorithmique category-fr:Théorie_de_la_complexité_des_algorithmes |
| rdfs:comment |
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) |
| rdfs:label |
Average-case complexity (en) Complexité en moyenne des algorithmes (fr) |
| owl:sameAs |
dbr:Average-case_complexity wikidata:Q4828244 dbpedia-pt:Complexidade_de_caso_médio dbpedia-ru:Сложность_алгоритма_в_среднем dbpedia-sr:Сложеност_просечног_случаја http://g.co/kg/m/04gg5fk http://ma-graph.org/entity/24604422 |
| prov:wasDerivedFrom |
wikipedia-fr:Complexité_en_moyenne_des_algorithmes?oldid=186972813&ns=0 |
| foaf:isPrimaryTopicOf |
wikipedia-fr:Complexité_en_moyenne_des_algorithmes |
| is dbo:wikiPageRedirects of |
dbpedia-fr:Complexité_en_moyenne |
| is dbo:wikiPageWikiLink of |
dbpedia-fr:Complexité_en_moyenne dbpedia-fr:Algorithme_de_Brzozowski_de_minimisation_d'un_automate_fini dbpedia-fr:Algorithme_de_Hopcroft-Karp dbpedia-fr:Algorithme_de_Hopcroft_de_minimisation_d'un_automate_fini dbpedia-fr:Algorithme_de_Moore_de_minimisation_d'un_automate_fini dbpedia-fr:Algorithme_de_sélection dbpedia-fr:Algorithme_de_tri dbpedia-fr:Analyse_amortie dbpedia-fr:Analyse_de_la_complexité_des_algorithmes dbpedia-fr:Analyse_lisse_d'algorithme dbpedia-fr:Complexité_algorithmique dbpedia-fr:Complexité_dans_le_meilleur_des_cas dbpedia-fr:Complexité_dans_le_pire_des_cas dbpedia-fr:Complexité_en_temps dbpedia-fr:Complexité_générique_des_algorithmes dbpedia-fr:Leonid_Levin dbpedia-fr:Luca_Trevisan dbpedia-fr:Optimisation_linéaire dbpedia-fr:Partition_binaire_de_l'espace dbpedia-fr:Philippe_Flajolet dbpedia-fr:Principe_de_Yao dbpedia-fr:Prix_Gödel dbpedia-fr:Quickhull dbpedia-fr:Quickselect dbpedia-fr:Recherche_par_interpolation dbpedia-fr:Recherche_séquentielle dbpedia-fr:Tas_(informatique) dbpedia-fr:Tetravex dbpedia-fr:Tri_de_Shell dbpedia-fr:Tri_par_insertion dbpedia-fr:Tri_par_paquets dbpedia-fr:Tri_par_sélection dbpedia-fr:Tri_par_tas dbpedia-fr:Tri_rapide dbpedia-fr:Minimisation_d'un_automate_fini_déterministe |
| is oa:hasTarget of |
tag-fr:EnFrResource tag-fr:WdtFrResource |
| is foaf:primaryTopic of |
wikipedia-fr:Complexité_en_moyenne_des_algorithmes |