| Property |
Value |
| dbo:abstract
|
- En informatique, un tas de Fibonacci est une structure de données similaire au tas binomial, mais avec un meilleur temps d'exécution amorti. Les tas de Fibonacci ont été conçus par Michael L. Fredman et Robert E. Tarjan en 1984 et publiés pour la première fois dans un journal scientifique en 1987. Les tas de Fibonacci sont utilisés pour améliorer le temps asymptotique de l'algorithme de Dijkstra, qui calcule les plus courts chemins dans un graphe, et de l'algorithme de Prim, qui calcule l'arbre couvrant de poids minimal d'un graphe. Le nom de tas de Fibonacci vient des nombres de Fibonacci, qui sont utilisés pour calculer son temps d'exécution. En particulier, les opérations insertion, trouver le minimum, décroître une clé, et union ont toutes un coût amorti constant. Les opérations supprimer et supprimer le minimum ont un coût amorti en O(log n). C'est-à-dire qu'en partant d'une structure vide, n'importe quelle séquence de a opérations du premier groupe et b opérations du second groupe prendrait un temps O(a + (b log n)). Dans un tas binomial, une telle séquence d'opérations prendrait un temps O((a + b)(log n)). Il devient donc plus intéressant d'utiliser un tas de Fibonacci plutôt qu'un tas binomial lorsque b est asymptotiquement plus petit que a. (fr)
- En informatique, un tas de Fibonacci est une structure de données similaire au tas binomial, mais avec un meilleur temps d'exécution amorti. Les tas de Fibonacci ont été conçus par Michael L. Fredman et Robert E. Tarjan en 1984 et publiés pour la première fois dans un journal scientifique en 1987. Les tas de Fibonacci sont utilisés pour améliorer le temps asymptotique de l'algorithme de Dijkstra, qui calcule les plus courts chemins dans un graphe, et de l'algorithme de Prim, qui calcule l'arbre couvrant de poids minimal d'un graphe. Le nom de tas de Fibonacci vient des nombres de Fibonacci, qui sont utilisés pour calculer son temps d'exécution. En particulier, les opérations insertion, trouver le minimum, décroître une clé, et union ont toutes un coût amorti constant. Les opérations supprimer et supprimer le minimum ont un coût amorti en O(log n). C'est-à-dire qu'en partant d'une structure vide, n'importe quelle séquence de a opérations du premier groupe et b opérations du second groupe prendrait un temps O(a + (b log n)). Dans un tas binomial, une telle séquence d'opérations prendrait un temps O((a + b)(log n)). Il devient donc plus intéressant d'utiliser un tas de Fibonacci plutôt qu'un tas binomial lorsque b est asymptotiquement plus petit que a. (fr)
|
| dbo:discoverer
| |
| dbo:namedAfter
| |
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 11652 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:titre
|
- Implémentation en C d'un tas de Fibonacci (fr)
- Implémentation en C d'un tas de Fibonacci (fr)
|
| prop-fr:url
| |
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- En informatique, un tas de Fibonacci est une structure de données similaire au tas binomial, mais avec un meilleur temps d'exécution amorti. Les tas de Fibonacci ont été conçus par Michael L. Fredman et Robert E. Tarjan en 1984 et publiés pour la première fois dans un journal scientifique en 1987. Les tas de Fibonacci sont utilisés pour améliorer le temps asymptotique de l'algorithme de Dijkstra, qui calcule les plus courts chemins dans un graphe, et de l'algorithme de Prim, qui calcule l'arbre couvrant de poids minimal d'un graphe. (fr)
- En informatique, un tas de Fibonacci est une structure de données similaire au tas binomial, mais avec un meilleur temps d'exécution amorti. Les tas de Fibonacci ont été conçus par Michael L. Fredman et Robert E. Tarjan en 1984 et publiés pour la première fois dans un journal scientifique en 1987. Les tas de Fibonacci sont utilisés pour améliorer le temps asymptotique de l'algorithme de Dijkstra, qui calcule les plus courts chemins dans un graphe, et de l'algorithme de Prim, qui calcule l'arbre couvrant de poids minimal d'un graphe. (fr)
|
| rdfs:label
|
- Fibonacci heap (en)
- Tas de Fibonacci (fr)
- Фибоначчиева куча (ru)
- Фібоначчієва купа (uk)
|
| rdfs:seeAlso
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
