| Property |
Value |
| 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)
- 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
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 5021 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1992 (xsd:integer)
- 2003 (xsd:integer)
- 2006 (xsd:integer)
|
| prop-fr:auteur
| |
| prop-fr:chapitre
| |
| prop-fr:jour
| |
| prop-fr:lireEnLigne
| |
| prop-fr:mois
|
- décembre (fr)
- mai (fr)
- décembre (fr)
- mai (fr)
|
| prop-fr:nom
|
- Li (fr)
- Delahaye (fr)
- Vitanyi (fr)
- 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)
- 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)
- 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)
- 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)
- 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
|
- 2 (xsd:integer)
- 42 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
| |
| dct:subject
| |
| 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)
- 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
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
