Attributes | Values |
---|
rdfs:label
| - Average-case complexity (en)
- Complexité en moyenne des algorithmes (fr)
|
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)
|
sameAs
| |
Wikipage page ID
| |
Wikipage revision ID
| |
dbo:wikiPageWikiLink
| |
Link from a Wikipage to an external page
| |
page length (characters) of wiki page
| |
dct:subject
| |
prop-fr:wikiPageUsesTemplate
| |
prov:wasDerivedFrom
| |
prop-fr:année
| |
prop-fr:auteur
| |
prop-fr:jour
| |
prop-fr:lireEnLigne
| |
prop-fr:mois
| |
prop-fr:nom
| - Li (fr)
- Delahaye (fr)
- Vitanyi (fr)
|
prop-fr:numéro
| |
prop-fr:pages
| |
prop-fr:passage
| |
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
| |
prop-fr:volume
| |
prop-fr:éditeur
| |
prop-fr:chapitre
| |
foaf:isPrimaryTopicOf
| |
has 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)
|
is dbo:wikiPageWikiLink
of | |